Extending immutable map
912 views
Skip to first unread message
Bruno Woltzenlogel Paleo
Jun 25, 2012, 8:10:00 AM6/25/12
to scala...@googlegroups.com
Hi,
I have just found this nice article containing an example of how to implement a simple subclass of mutable Map: http://www.artima.com/scalazine/articles/scala_collections_architectureP.html
My question is: where can I find a similar simple example for extending *immutable* map?
Best regards,
Bruno
Daniel Sobral
Jun 25, 2012, 9:18:17 AM6/25/12
to Bruno Woltzenlogel Paleo, scala...@googlegroups.com
There's no significant difference between extending a mutable or an
immutable collection. That was one of the design goals of the
collections, in fact.
--
Daniel C. Sobral
I travel to the future all the time.
immutable collection. That was one of the design goals of the
collections, in fact.
Daniel C. Sobral
I travel to the future all the time.
Bruno Woltzenlogel Paleo
Jun 25, 2012, 10:20:30 AM6/25/12
to Daniel Sobral, scala...@googlegroups.com
There's no significant difference between extending a mutable or an
immutable collection. That was one of the design goals of the
collections, in fact.
Thanks for the answer, Daniel Sobral.
Somehow, it is harder for me to extend immutable map, because the method "+" seems a bit more complicated to implement than the corresponding mutable method "+=". Right now, I make it work with a dynamic casting (see the commented line in the code snippet below, if you have time/interest). But is there a more elegant/correct way to do this?
Also, it is not as clear to me how to implement the companion object methods "newBuilder" and "canBuildFrom" (Should I implement them? Why? Could you point me a good reference to learn more about this?). In the mutable case (as explained here: http://www.artima.com/scalazine/articles/scala_collections_architectureP.html), their implementation used "mutable.Builder" and "mutable.MapBuilder". What are the immutable classes that correspond to "mutable.Builder" and "mutable.MapBuilder" and that I should use to implement "newBuilder" and "canBuildFrom"?
Thanks,
Best regards,
Bruno
class Substitution(override protected val m: Map[Var, E])
extends AbstractSubstitution with Map[Var, E] with MapLike[Var, E, Substitution] {
def get(key: Var) = m.get(key)
def iterator: Iterator[(Var, E)] = m.iterator
def + [B >: E](kv: (Var, B)) = new Substitution(m + kv.asInstanceOf[(Var,E)]) // Is there a more elegant/correct way to do this?
def - (key: Var) = new Substitution(m - key)
override def empty = new Substitution(Map[Var,E]())
}
object Substitution {
def empty = new Substitution(Map[Var,E]())
def apply(kvs: (Var, E)*): Substitution = new Substitution(Map[Var,E](kvs:_*))
}
Daniel Sobral
Jun 25, 2012, 12:59:40 PM6/25/12
to Bruno Woltzenlogel Paleo, scala...@googlegroups.com
On Mon, Jun 25, 2012 at 11:20 AM, Bruno Woltzenlogel Paleo
<brun...@gmail.com> wrote:
>
> Somehow, it is harder for me to extend immutable map, because the method "+"
> seems a bit more complicated to implement than the corresponding mutable
> method "+=". Right now, I make it work with a dynamic casting (see the
> commented line in the code snippet below, if you have time/interest). But is
> there a more elegant/correct way to do this?
Yes. Remove the casting.
<brun...@gmail.com> wrote:
>
> Somehow, it is harder for me to extend immutable map, because the method "+"
> seems a bit more complicated to implement than the corresponding mutable
> method "+=". Right now, I make it work with a dynamic casting (see the
> commented line in the code snippet below, if you have time/interest). But is
> there a more elegant/correct way to do this?
> Also, it is not as clear to me how to implement the companion object methods
> "newBuilder" and "canBuildFrom" (Should I implement them? Why? Could you
> point me a good reference to learn more about this?). In the mutable case
> class Substitution(override protected val m: Map[Var, E])
> extends AbstractSubstitution with Map[Var, E] with MapLike[Var, E,
> Substitution] {
> def get(key: Var) = m.get(key)
> def iterator: Iterator[(Var, E)] = m.iterator
> def + [B >: E](kv: (Var, B)) = new Substitution(m +
> kv.asInstanceOf[(Var,E)]) // Is there a more elegant/correct way to do this?
I suggest you look at Scala libraries as example. See, for instance,
that object HashMap
(http://www.scala-lang.org/archives/downloads/distrib/files/nightly/docs/library/index.html#scala.collection.immutable.HashMap$)
does not implement itself newBuilder: it receives it from
GenMapFactory, through its ImmutableMapFactory parent.
Bjorn Regnell
Jun 25, 2012, 4:10:45 PM6/25/12
to scala-user
Hi,
I am struggling with a similar problem; I'm trying to build an
immutable Bag[K,E] by extending Map and MapLike to include a
Map(K,Set[E]).
This is my attempt after some head scratching:
---
class Bag[K, E]( val mapToSets: scala.collection.immutable.Map[K,
Set[E]])
extends scala.collection.immutable.Map[K, Set[E]]
with scala.collection.immutable.MapLike[K, Set[E], Bag[K, E]] {
def get(key: K):Option[Set[E]] = mapToSets.get(key)
override def empty = new Bag[K, E](Map.empty)
def +[B1 >: E](kv: (K, B1)): Bag[K, B1] = {
val (k, e) = (kv._1, kv._2)
val es = if (!mapToSets.isDefinedAt(k)) Set(e) else mapToSets(k)
++ Set(e)
new Bag[K, B1](mapToSets + (k, es))
}
def -(k: K) = new Bag(mapToSets - k)
def iterator:Iterator[(K, Set[E])] = mapToSets.iterator
override def stringPrefix = "Bag"
}
object Bag extends {
import scala.collection.mutable.{Builder, MapBuilder}
import scala.collection.generic.CanBuildFrom
def empty[K, E] = new Bag[K, E](Map.empty)
def apply[K, E](kvs: (K, E)*): Bag[K, E] = {
var a : Bag[K, E] = empty
for (kv <- kvs) a = a + kv
a
}
def newBuilder[K, E]: Builder[(K, E), Bag[K, E]] =
new MapBuilder[K, E, Bag[K, E]](empty)
implicit def canBuildFrom[K, E]
: CanBuildFrom[Bag[_, _], (K, E), Bag[K, E]] =
new CanBuildFrom[Bag[_, _], (K, E), Bag[K, E]] {
def apply(from: Bag[_,_]) = newBuilder[K, E]
def apply() = newBuilder[K, E]
}
}
---
error: type mismatch;
found :
scala.collection.immutable.Map[K,scala.collection.immutable.Set[_ >: E
<: B1]]
required: scala.collection.immutable.Map[K,Set[B1]]
new Bag[K, B1](mapToSets + (k, es))
---
Any ideas of how to solve this or perhaps an explanation of why I'm
doing it the wrong way?
/Bjorn Regnell
On 25 Juni, 18:59, Daniel Sobral <dcsob...@gmail.com> wrote:
> On Mon, Jun 25, 2012 at 11:20 AM, Bruno Woltzenlogel Paleo
>
I am struggling with a similar problem; I'm trying to build an
immutable Bag[K,E] by extending Map and MapLike to include a
Map(K,Set[E]).
This is my attempt after some head scratching:
---
class Bag[K, E]( val mapToSets: scala.collection.immutable.Map[K,
Set[E]])
extends scala.collection.immutable.Map[K, Set[E]]
with scala.collection.immutable.MapLike[K, Set[E], Bag[K, E]] {
def get(key: K):Option[Set[E]] = mapToSets.get(key)
override def empty = new Bag[K, E](Map.empty)
def +[B1 >: E](kv: (K, B1)): Bag[K, B1] = {
val (k, e) = (kv._1, kv._2)
val es = if (!mapToSets.isDefinedAt(k)) Set(e) else mapToSets(k)
++ Set(e)
new Bag[K, B1](mapToSets + (k, es))
}
def -(k: K) = new Bag(mapToSets - k)
def iterator:Iterator[(K, Set[E])] = mapToSets.iterator
override def stringPrefix = "Bag"
}
object Bag extends {
import scala.collection.mutable.{Builder, MapBuilder}
import scala.collection.generic.CanBuildFrom
def empty[K, E] = new Bag[K, E](Map.empty)
def apply[K, E](kvs: (K, E)*): Bag[K, E] = {
var a : Bag[K, E] = empty
for (kv <- kvs) a = a + kv
a
}
def newBuilder[K, E]: Builder[(K, E), Bag[K, E]] =
new MapBuilder[K, E, Bag[K, E]](empty)
implicit def canBuildFrom[K, E]
: CanBuildFrom[Bag[_, _], (K, E), Bag[K, E]] =
new CanBuildFrom[Bag[_, _], (K, E), Bag[K, E]] {
def apply(from: Bag[_,_]) = newBuilder[K, E]
def apply() = newBuilder[K, E]
}
}
---
error: type mismatch;
found :
scala.collection.immutable.Map[K,scala.collection.immutable.Set[_ >: E
<: B1]]
required: scala.collection.immutable.Map[K,Set[B1]]
new Bag[K, B1](mapToSets + (k, es))
---
Any ideas of how to solve this or perhaps an explanation of why I'm
doing it the wrong way?
/Bjorn Regnell
On 25 Juni, 18:59, Daniel Sobral <dcsob...@gmail.com> wrote:
> On Mon, Jun 25, 2012 at 11:20 AM, Bruno Woltzenlogel Paleo
>
> <bruno...@gmail.com> wrote:
>
> > Somehow, it is harder for me to extend immutable map, because the method "+"
> > seems a bit more complicated to implement than the corresponding mutable
> > method "+=". Right now, I make it work with a dynamic casting (see the
> > commented line in the code snippet below, if you have time/interest). But is
> > there a more elegant/correct way to do this?
>
> Yes. Remove the casting.
>
> > Also, it is not as clear to me how to implement the companion object methods
> > "newBuilder" and "canBuildFrom" (Should I implement them? Why? Could you
> > point me a good reference to learn more about this?). In the mutable case
>
> Yes, you should, because that's how all collections work.
>
> > class Substitution(override protected val m: Map[Var, E])
> > extends AbstractSubstitution with Map[Var, E] with MapLike[Var, E,
> > Substitution] {
> > def get(key: Var) = m.get(key)
> > def iterator: Iterator[(Var, E)] = m.iterator
> > def + [B >: E](kv: (Var, B)) = new Substitution(m +
> > kv.asInstanceOf[(Var,E)]) // Is there a more elegant/correct way to do this?
>
> Remove the casting. The method + should return Map[Var, B], not Map[Var, E].
>
> I suggest you look at Scala libraries as example. See, for instance,
> that object HashMap
> (http://www.scala-lang.org/archives/downloads/distrib/files/nightly/do...)
>
> > Somehow, it is harder for me to extend immutable map, because the method "+"
> > seems a bit more complicated to implement than the corresponding mutable
> > method "+=". Right now, I make it work with a dynamic casting (see the
> > commented line in the code snippet below, if you have time/interest). But is
> > there a more elegant/correct way to do this?
>
> Yes. Remove the casting.
>
> > Also, it is not as clear to me how to implement the companion object methods
> > "newBuilder" and "canBuildFrom" (Should I implement them? Why? Could you
> > point me a good reference to learn more about this?). In the mutable case
>
> Yes, you should, because that's how all collections work.
>
> > class Substitution(override protected val m: Map[Var, E])
> > extends AbstractSubstitution with Map[Var, E] with MapLike[Var, E,
> > Substitution] {
> > def get(key: Var) = m.get(key)
> > def iterator: Iterator[(Var, E)] = m.iterator
> > def + [B >: E](kv: (Var, B)) = new Substitution(m +
> > kv.asInstanceOf[(Var,E)]) // Is there a more elegant/correct way to do this?
>
> Remove the casting. The method + should return Map[Var, B], not Map[Var, E].
>
> I suggest you look at Scala libraries as example. See, for instance,
> that object HashMap
Daniel Sobral
Jun 25, 2012, 4:23:04 PM6/25/12
to Bjorn Regnell, scala-user
Map is covariant in B (Map[A, +B]), while Set isn't. The fact that Set
is not covariant allows it to define "+" like this:
override def + (e: A): HashSet[A] = updated0(e, computeHash(e), 0)
Unfortunately, you can't get away with that on Map. Right now, I can
only think of recreating the whole Set (ie, adding all its elements to
a new Set of the proper type), which is a pretty lousy solution. Let's
see if someone doesn't have a suggestion to make here.
is not covariant allows it to define "+" like this:
override def + (e: A): HashSet[A] = updated0(e, computeHash(e), 0)
Unfortunately, you can't get away with that on Map. Right now, I can
only think of recreating the whole Set (ie, adding all its elements to
a new Set of the proper type), which is a pretty lousy solution. Let's
see if someone doesn't have a suggestion to make here.
Bruno Woltzenlogel Paleo
Jun 26, 2012, 3:12:42 AM6/26/12
to Daniel Sobral, scala...@googlegroups.com
Also, it is not as clear to me how to implement the companion object methods"newBuilder" and "canBuildFrom" (Should I implement them? Why? Could youpoint me a good reference to learn more about this?). In the mutable case
Yes, you should, because that's how all collections work.
Ok. I did it as I had done for the mutable case. I can see now why you said that there's no significant difference between extending a mutable or an
immutable collection. I was confused at first, because I thought I would need something immutable corresponding to Builder and MapBuilder. But now I understand that this wouldn't really make sense.def + [B >: E](kv: (Var, B)) = new Substitution(m +kv.asInstanceOf[(Var,E)]) // Is there a more elegant/correct way to do this?
Remove the casting. The method + should return Map[Var, B], not Map[Var, E].
If I simply remove the casting (i.e.: def + [B >: E](kv: (Var, B)) = m + kv ), I get an exception whenever I try to use methods like "map":
val s = Substitution(Var("a",i) -> Var("b", o))
val z = s map { case (a,b) => (a,Var("n",i)) }
ClassCastException: scala.collection.immutable.Map$Map1 cannot be cast to Substitution
Then I tried to replace the casting by pattern matching, as follows:
def + [B >: E](kv: (Var, B)) = kv match {
case kv: (Var, E) => new Substitution(m + kv)
case _ => m + kv
}
And this makes methods like "map" behave as expected. But due to type erasure, kv will always match the first case, and a new Substitution will be created even when the value is not of type E!
So, right now I'm doing this:
def + [B >: E](kv: (Var, B)) = if (kv._2.isInstanceOf[E]) new Substitution(m + kv.asInstanceOf[(Var,E)])
else m + kv
And everything works as I expect. But again, is there a more elegant/correct way to do this?
Best regards,
PS: The full code can be seen here:
These classes are part of a project that compresses formal proofs output by Sat- and SMT-solvers.
Bruno
Bruno
Jun 26, 2012, 4:32:01 PM6/26/12
to scala...@googlegroups.com
Hi,
def +[B1 >: E](kv: (K, B1)): Bag[K, B1] = {
val (k, e) = (kv._1, kv._2)
val es = if (!mapToSets.isDefinedAt(k)) Set(e) else mapToSets(k)
++ Set(e)
new Bag[K, B1](mapToSets + (k, es))
}
error: type mismatch;
found :
scala.collection.immutable.Map[K,scala.collection.immutable.Set[_ >: E
<: B1]]
required: scala.collection.immutable.Map[K,Set[B1]]
new Bag[K, B1](mapToSets + (k, es))
---
Any ideas of how to solve this or perhaps an explanation of why I'm
doing it the wrong way?
I guess this has to do with the fact that Set is not covariant.
If it were covariant, Set[_ >: E <: B1] would be a subtype of the required Set[B1], and there would be no type mismatch.
I hope this partial answer helps...
Best regards,
Bruno
Bjorn Regnell
Jun 26, 2012, 4:35:03 PM6/26/12
to scala-user
Bruno,
in your code:
final class Substitution (override protected val m: Map[Var, E]) ...
Perhaps you need to make E a type parameter:
final class Substitution[E] (override protected val m: Map[Var,
E]) ...
?
/Bjorn
On 26 Juni, 09:12, Bruno Woltzenlogel Paleo <bruno...@gmail.com>
wrote:
in your code:
final class Substitution (override protected val m: Map[Var, E]) ...
Perhaps you need to make E a type parameter:
final class Substitution[E] (override protected val m: Map[Var,
E]) ...
?
/Bjorn
On 26 Juni, 09:12, Bruno Woltzenlogel Paleo <bruno...@gmail.com>
wrote:
> >> Also, it is not as clear to me how to implement the companion object methods
> >> "newBuilder" and "canBuildFrom" (Should I implement them? Why? Could you
> >> point me a good reference to learn more about this?). In the mutable case
>
> > Yes, you should, because that's how all collections work.
>
> Ok. I did it as I had done for the mutable case. I can see now why you said that there's no significant difference between extending a mutable or an
> immutable collection. I was confused at first, because I thought I would need something immutable corresponding to Builder and MapBuilder. But now I understand that this wouldn't really make sense.
>
> >> def + [B >: E](kv: (Var, B)) = new Substitution(m +
> >> kv.asInstanceOf[(Var,E)]) // Is there a more elegant/correct way to do this?
>
> > Remove the casting. The method + should return Map[Var, B], not Map[Var, E].
>
> If I simply remove the casting (i.e.: def + [B >: E](kv: (Var, B)) = m + kv ), I get an exception whenever I try to use methods like "map":
>
> val s = Substitution(Var("a",i) -> Var("b", o))
> val z = s map { case (a,b) => (a,Var("n",i)) }
>
> ClassCastException: scala.collection.immutable.Map$Map1 cannot be cast to Substitution
>
> Then I tried to replace the casting by pattern matching, as follows:
>
> def + [B >: E](kv: (Var, B)) = kv match {
> case kv: (Var, E) => new Substitution(m + kv)
> case _ => m + kv
> }
>
> And this makes methods like "map" behave as expected. But due to type erasure, kv will always match the first case, and a new Substitution will be created even when the value is not of type E!
>
> So, right now I'm doing this:
>
> def + [B >: E](kv: (Var, B)) = if (kv._2.isInstanceOf[E]) new Substitution(m + kv.asInstanceOf[(Var,E)])
> else m + kv
>
> And everything works as I expect. But again, is there a more elegant/correct way to do this?
>
> Thank you very much for your help!
>
> Best regards,
>
> PS: The full code can be seen here:https://github.com/Paradoxika/Skeptik/blob/master/src/main/scala/skep...https://github.com/Paradoxika/Skeptik/blob/master/src/main/scala/skep...
> >> "newBuilder" and "canBuildFrom" (Should I implement them? Why? Could you
> >> point me a good reference to learn more about this?). In the mutable case
>
> > Yes, you should, because that's how all collections work.
>
> Ok. I did it as I had done for the mutable case. I can see now why you said that there's no significant difference between extending a mutable or an
> immutable collection. I was confused at first, because I thought I would need something immutable corresponding to Builder and MapBuilder. But now I understand that this wouldn't really make sense.
>
> >> def + [B >: E](kv: (Var, B)) = new Substitution(m +
> >> kv.asInstanceOf[(Var,E)]) // Is there a more elegant/correct way to do this?
>
> > Remove the casting. The method + should return Map[Var, B], not Map[Var, E].
>
> If I simply remove the casting (i.e.: def + [B >: E](kv: (Var, B)) = m + kv ), I get an exception whenever I try to use methods like "map":
>
> val s = Substitution(Var("a",i) -> Var("b", o))
> val z = s map { case (a,b) => (a,Var("n",i)) }
>
> ClassCastException: scala.collection.immutable.Map$Map1 cannot be cast to Substitution
>
> Then I tried to replace the casting by pattern matching, as follows:
>
> def + [B >: E](kv: (Var, B)) = kv match {
> case kv: (Var, E) => new Substitution(m + kv)
> case _ => m + kv
> }
>
> And this makes methods like "map" behave as expected. But due to type erasure, kv will always match the first case, and a new Substitution will be created even when the value is not of type E!
>
> So, right now I'm doing this:
>
> def + [B >: E](kv: (Var, B)) = if (kv._2.isInstanceOf[E]) new Substitution(m + kv.asInstanceOf[(Var,E)])
> else m + kv
>
> And everything works as I expect. But again, is there a more elegant/correct way to do this?
>
> Thank you very much for your help!
>
> Best regards,
>
Bjorn Regnell
Jun 26, 2012, 4:37:47 PM6/26/12
to scala-user
Thanks, Bruno. Yes that explains it. I'll solve it with a check and
cast... I know the types I'll use anyway so I can hard code it.
Annoying though...
/Bjorn
> Bruno- Dölj citerad text -
>
> - Visa citerad text -
cast... I know the types I'll use anyway so I can hard code it.
Annoying though...
/Bjorn
>
> - Visa citerad text -
Reply all
Reply to author
Forward
0 new messages