|
View:
New views
10 Messages
—
Rating Filter:
Alert me
|
|
|
MultiMap with a List instead of a Set?I'm using 2.7.7 and I note that:
trait MultiMap[A, B] extends Map[A, Set[B]] I was wondering why a Set is used specifically, rather than something more general? Reason is...I have a case where I need to associate a number of values to the same key. E.g., "values" -> List(true,true,false,true) where the ordering of the values is important, and can be repeated (I guess I mean ListBuffer, but you get the idea). Of course, with a MutiMap backed by a mutable Set I end up with "values" -> Set(true,false) with the other two values dropped. Is it a terminology thing? Maybe I should be looking for some other kind of MultiX data structure... or perhaps I'm missing a trick on how to achieve what I want with a MultiMap Thanks Richard $ scala Welcome to Scala version 2.7.7.final (Java HotSpot(TM) 64-Bit Server VM, Java 1.6.0_15). Type in expressions to have them evaluated. Type :help for more information. scala> import scala.collection.mutable.{Set => MSet, HashMap, MultiMap} import scala.collection.mutable.{Set=>MSet, HashMap, MultiMap} scala> val m:MultiMap[String,String] = new HashMap[String, MSet[String]] with MultiMap[String, String] m: scala.collection.mutable.MultiMap[String,String] = Map() scala> m.add("values", "true") scala> m.add("values", "true") scala> m.add("values", "false") scala> m.add("values", "true") scala> m res4: scala.collection.mutable.MultiMap[String,String] = Map(values -> Set(false, true)) scala> |
|
|
Re: MultiMap with a List instead of a Set?It's a terminology thing. There's no general agreement on exactly what the semantics of "multi" are. Google Collections, for instance, has both set and list based versions: http://google-collections.googlecode.com/svn/trunk/javadoc/com/google/common/collect/Multimap.html . Bag based versions would make sense, too.
On Wed, Nov 4, 2009 at 8:12 AM, Richard Dallaway <dallaway@...> wrote: Is it a terminology thing? Maybe I should be looking for some other |
|
|
Re: MultiMap with a List instead of a Set?On Wed, Nov 04, 2009 at 04:12:46PM +0000, Richard Dallaway wrote:
> I'm using 2.7.7 and I note that: > > trait MultiMap[A, B] extends Map[A, Set[B]] > > I was wondering why a Set is used specifically, rather than something > more general? In 2.7 being more general there was difficult. It's still difficult, but in more of a "figure out how to do it" way instead of a "man, if only I had more powerful abstractions" way. I'm not too proud of this (not a finished product) but as a demo, here's a rewrite of MultiMap in trunk which parameterizes the value container. package scala.collection package mutable import generic.{ Addable, Subtractable } import scala.{ collection => col } trait MultiMap[A, B, Coll <: Addable[B, Coll] with Subtractable[B, Coll] with col.Iterable[B] with col.IterableLike[B, Coll]] extends Map[A, Coll] { protected def emptyContainer: Coll def addBinding(key: A, value: B): this.type = { get(key) match { case None => this(key) = emptyContainer + value case Some(_) => this(key) += value } this } def removeBinding(key: A, value: B): this.type = { get(key) match { case None => case Some(_) => this(key) -= value } this } def entryExists(key: A, p: B => Boolean): Boolean = get(key) match { case None => false case Some(values) => values exists p } } ... and it goes like this. (In 2.8 add was renamed to addBinding.) scala> import scala.collection.mutable._ import scala.collection.mutable._ scala> val m = new HashMap[String, ListBuffer[String]] with MultiMap[String, String, ListBuffer[String]] { def emptyContainer = ListBuffer() } m: scala.collection.mutable.HashMap[String,scala.collection.mutable.ListBuffer[String]] with scala.collection.mutable.MultiMap[String,String,scala.collection.mutable.ListBuffer[String]] = Map() scala> m.addBinding("values", "true") res1: m.type = Map(values -> ListBuffer(true)) scala> m.addBinding("values", "true") res2: m.type = Map(values -> ListBuffer(true, true)) scala> m.addBinding("values", "false") res3: m.type = Map(values -> ListBuffer(true, true, false)) -- Paul Phillips | Simplicity and elegance are unpopular because Vivid | they require hard work and discipline to achieve Empiricist | and education to be appreciated. slap pi uphill! | -- Dijkstra |
|
|
Re: MultiMap with a List instead of a Set?Perhaps you could store (Int, Boolean) tuples in to the MultiMap, where
the integer value is an index value you can then use to order the
members of each individual Set on. You could use a single integer
variable to assign unique values to each Boolean as its added to the
MultiMap.
(Longer explanation...) I think the purpose of the MultiMap class it to implement the concept of a multi-valued function that exists in set theory. In set theory, a normal function is a mapping from a domain D to a range R (i.e., "D => R"), and it can be thought of as a set of (D, R) pairs. A multi-valued function is a mapping from the domain D to the power set of range R (i.e., "D => P(R)"). That is, the multi-valued function can be thought of as a set of (D, R^n) pairs. Scala's MultiMap is an implementation of this concept where the member pairs are explicitly computed and "remembered" in the container. In math/logic, one way to define lists is as a set of (index, value) pairs where the indexes are unique in the collection. So in Scala you can to do the same thing: define the value members of the MultiMap value sets to be Pair[Int, Boolean] instead of just Boolean. So the MultiMap type is MultiMap[KeyType, Pair[Int, Boolean]]. Just make sure to assign an integer value to each boolean value when you insert it in to the MultiMap; one easy-to-code way would be to use a single counter variable. Best regards, Brian Maso (949) 395-8551 brian@... twitter: @bmaso skype: brian.maso LinkedIn: http://www.linkedin.com/in/brianmaso On Wed, Nov 4, 2009 at 8:12 AM, Richard Dallaway <dallaway@...> wrote: I'm using 2.7.7 and I note that: |
|
|
Re: MultiMap with a List instead of a Set?The problem is not "how to model a List using a Set" - otherwise he
could just be wrapping the values in objects with equals() based on identity (to avoid clumsy unique integer id assignments). A list may have a fast positional lookup though which a Set typically lacks - so the type indirectly affects the representation, representation dictates performance, and that's a desicion that shouldn't be fixed, the user must make that desicion, because there is no one-size-fits-all solution. I hope scala collections are not rushed and cast on stone early, the risk is just too big. Google collections have gone through a cycle of very heavy usage for years before stabilizing (and still they haven't published a final 1.0 version). It's a tough versioning problem. By the way, a problem with Multimap in google collections is that the type of values is "Collection", and there are various subinterfaces which specialize it to "Set" (SetMultimap), "List" (ListMultimap), "SortedSet" (etc) - I'm pretty sure scala has the abstractions to sort this while avoiding such a proliferation of types. Does anyone know if there a roadmap on scala collections? I think the community should also help in development of an elaborate test suite, to reach the standards of google collections test suite. Regards, Dimitris 2009/11/5 Brian Maso <brian@...>: > Perhaps you could store (Int, Boolean) tuples in to the MultiMap, where the > integer value is an index value you can then use to order the members of > each individual Set on. You could use a single integer variable to assign > unique values to each Boolean as its added to the MultiMap. > > (Longer explanation...) > I think the purpose of the MultiMap class it to implement the concept of a > multi-valued function that exists in set theory. In set theory, a normal > function is a mapping from a domain D to a range R (i.e., "D => R"), and it > can be thought of as a set of (D, R) pairs. A multi-valued function is a > mapping from the domain D to the power set of range R (i.e., "D => P(R)"). > That is, the multi-valued function can be thought of as a set of (D, R^n) > pairs. Scala's MultiMap is an implementation of this concept where the > member pairs are explicitly computed and "remembered" in the container. > > In math/logic, one way to define lists is as a set of (index, value) pairs > where the indexes are unique in the collection. So in Scala you can to do > the same thing: define the value members of the MultiMap value sets to be > Pair[Int, Boolean] instead of just Boolean. So the MultiMap type is > MultiMap[KeyType, Pair[Int, Boolean]]. Just make sure to assign an integer > value to each boolean value when you insert it in to the MultiMap; one > easy-to-code way would be to use a single counter variable. > > Best regards, > Brian Maso > (949) 395-8551 > brian@... > twitter: @bmaso > skype: brian.maso > LinkedIn: http://www.linkedin.com/in/brianmaso > > On Wed, Nov 4, 2009 at 8:12 AM, Richard Dallaway <dallaway@...> wrote: >> >> I'm using 2.7.7 and I note that: >> >> trait MultiMap[A, B] extends Map[A, Set[B]] >> >> I was wondering why a Set is used specifically, rather than something >> more general? >> >> Reason is...I have a case where I need to associate a number of values >> to the same key. E.g., "values" -> List(true,true,false,true) where >> the ordering of the values is important, and can be repeated (I guess >> I mean ListBuffer, but you get the idea). Of course, with a MutiMap >> backed by a mutable Set I end up with "values" -> Set(true,false) with >> the other two values dropped. >> >> Is it a terminology thing? Maybe I should be looking for some other >> kind of MultiX data structure... or perhaps I'm missing a trick on how >> to achieve what I want with a MultiMap >> >> Thanks >> Richard >> >> >> $ scala >> Welcome to Scala version 2.7.7.final (Java HotSpot(TM) 64-Bit Server >> VM, Java 1.6.0_15). >> Type in expressions to have them evaluated. >> Type :help for more information. >> >> scala> import scala.collection.mutable.{Set => MSet, HashMap, MultiMap} >> import scala.collection.mutable.{Set=>MSet, HashMap, MultiMap} >> >> scala> val m:MultiMap[String,String] = new HashMap[String, >> MSet[String]] with MultiMap[String, String] >> m: scala.collection.mutable.MultiMap[String,String] = Map() >> >> scala> m.add("values", "true") >> >> scala> m.add("values", "true") >> >> scala> m.add("values", "false") >> >> scala> m.add("values", "true") >> >> scala> m >> res4: scala.collection.mutable.MultiMap[String,String] = Map(values -> >> Set(false, true)) >> >> scala> > > |
|
|
Re: MultiMap with a List instead of a Set?I've been struggling with this for a while. It seems that simply with'ing a trait with 'addBinding' and such only works for, well, adding stuff. But for methods like 'map' elements added to the returned multimap do not use 'addBinding', resulting the overwriting of key values. (Could it be that I am I missing something?)
|
|
|
Re: MultiMap with a List instead of a Set?Is this the kind of thing I should I be raising this as a ticket in
Trac? It seems like a generally useful enhancement. Thank you Richard On Wed, Nov 4, 2009 at 5:43 PM, Paul Phillips <paulp@...> wrote: > On Wed, Nov 04, 2009 at 04:12:46PM +0000, Richard Dallaway wrote: >> I'm using 2.7.7 and I note that: >> >> trait MultiMap[A, B] extends Map[A, Set[B]] >> >> I was wondering why a Set is used specifically, rather than something >> more general? > > In 2.7 being more general there was difficult. It's still difficult, > but in more of a "figure out how to do it" way instead of a "man, if > only I had more powerful abstractions" way. I'm not too proud of this > (not a finished product) but as a demo, here's a rewrite of MultiMap in > trunk which parameterizes the value container. > > package scala.collection > package mutable > > import generic.{ Addable, Subtractable } > import scala.{ collection => col } > > trait MultiMap[A, B, Coll <: Addable[B, Coll] with Subtractable[B, Coll] with col.Iterable[B] with col.IterableLike[B, Coll]] extends Map[A, Coll] { > protected def emptyContainer: Coll > > def addBinding(key: A, value: B): this.type = { > get(key) match { > case None => this(key) = emptyContainer + value > case Some(_) => this(key) += value > } > this > } > > def removeBinding(key: A, value: B): this.type = { > get(key) match { > case None => > case Some(_) => this(key) -= value > } > this > } > > def entryExists(key: A, p: B => Boolean): Boolean = get(key) match { > case None => false > case Some(values) => values exists p > } > } > > > ... and it goes like this. (In 2.8 add was renamed to addBinding.) > > > scala> import scala.collection.mutable._ > import scala.collection.mutable._ > > scala> val m = new HashMap[String, ListBuffer[String]] with MultiMap[String, String, ListBuffer[String]] { def emptyContainer = ListBuffer() } > m: scala.collection.mutable.HashMap[String,scala.collection.mutable.ListBuffer[String]] with scala.collection.mutable.MultiMap[String,String,scala.collection.mutable.ListBuffer[String]] = Map() > > scala> m.addBinding("values", "true") > res1: m.type = Map(values -> ListBuffer(true)) > > scala> m.addBinding("values", "true") > res2: m.type = Map(values -> ListBuffer(true, true)) > > scala> m.addBinding("values", "false") > res3: m.type = Map(values -> ListBuffer(true, true, false)) > > -- > Paul Phillips | Simplicity and elegance are unpopular because > Vivid | they require hard work and discipline to achieve > Empiricist | and education to be appreciated. > slap pi uphill! | -- Dijkstra > |
|
|
RE: MultiMap with a List instead of a Set?> Is this the kind of thing I should I be raising this as a ticket in > Trac? It seems like a generally useful enhancement. > > Thank you > Richard > > On Wed, Nov 4, 2009 at 5:43 PM, Paul Phillips <paulp@...> wrote: > > On Wed, Nov 04, 2009 at 04:12:46PM +0000, Richard Dallaway wrote: > >> I'm using 2.7.7 and I note that: > >> > >> trait MultiMap[A, B] extends Map[A, Set[B]] > >> > >> I was wondering why a Set is used specifically, rather than something > >> more general? > > > > In 2.7 being more general there was difficult. It's still difficult, > > but in more of a "figure out how to do it" way instead of a "man, if > > only I had more powerful abstractions" way. I'm not too proud of this > > (not a finished product) but as a demo, here's a rewrite of MultiMap in > > trunk which parameterizes the value container. > > > > package scala.collection > > package mutable > > > > import generic.{ Addable, Subtractable } > > import scala.{ collection => col } > > > > trait MultiMap[A, B, Coll <: Addable[B, Coll] with Subtractable[B, Coll] with col.Iterable[B] with col.IterableLike[B, Coll]] extends Map[A, Coll] { > > protected def emptyContainer: Coll > > > > def addBinding(key: A, value: B): this.type = { > > get(key) match { > > case None => this(key) = emptyContainer + value > > case Some(_) => this(key) += value > > } > > this > > } > > > > def removeBinding(key: A, value: B): this.type = { > > get(key) match { > > case None => > > case Some(_) => this(key) -= value > > } > > this > > } > > > > def entryExists(key: A, p: B => Boolean): Boolean = get(key) match { > > case None => false > > case Some(values) => values exists p > > } > > } > > > > > > ... and it goes like this. (In 2.8 add was renamed to addBinding.) > > > > > > scala> import scala.collection.mutable._ > > import scala.collection.mutable._ > > > > scala> val m = new HashMap[String, ListBuffer[String]] with MultiMap[String, String, ListBuffer[String]] { def emptyContainer = ListBuffer() } > > m: scala.collection.mutable.HashMap[String,scala.collection.mutable.ListBuffer[String]] with scala.collection.mutable.MultiMap[String,String,scala.collection.mutable.ListBuffer[String]] = Map() > > > > scala> m.addBinding("values", "true") > > res1: m.type = Map(values -> ListBuffer(true)) > > > > scala> m.addBinding("values", "true") > > res2: m.type = Map(values -> ListBuffer(true, true)) > > > > scala> m.addBinding("values", "false") > > res3: m.type = Map(values -> ListBuffer(true, true, false)) > > > > -- > > Paul Phillips | Simplicity and elegance are unpopular because > > Vivid | they require hard work and discipline to achieve > > Empiricist | and education to be appreciated. > > slap pi uphill! | -- Dijkstra > > Download Messenger onto your mobile for free. Learn more. |
|
|
|
|
|
Re: MultiMap with a List instead of a Set?Ticket raised. https://lampsvn.epfl.ch/trac/scala/ticket/2608
I hope we can find a way to make the improvement. Richard On Mon, Nov 9, 2009 at 6:08 PM, christopher marshall <oxbow_lakes@...> wrote: > I completely agree - I regularly use MultiMap-like functionality with List > instead of Set; a generalization of it would be really useful > >> Is this the kind of thing I should I be raising this as a ticket in >> Trac? It seems like a generally useful enhancement. >> >> Thank you >> Richard >> >> On Wed, Nov 4, 2009 at 5:43 PM, Paul Phillips <paulp@...> wrote: >> > On Wed, Nov 04, 2009 at 04:12:46PM +0000, Richard Dallaway wrote: >> >> I'm using 2.7.7 and I note that: >> >> >> >> trait MultiMap[A, B] extends Map[A, Set[B]] >> >> >> >> I was wondering why a Set is used specifically, rather than something >> >> more general? >> > >> > In 2.7 being more general there was difficult. It's still difficult, >> > but in more of a "figure out how to do it" way instead of a "man, if >> > only I had more powerful abstractions" way. I'm not too proud of this >> > (not a finished product) but as a demo, here's a rewrite of MultiMap in >> > trunk which parameterizes the value container. >> > >> > package scala.collection >> > package mutable >> > >> > import generic.{ Addable, Subtractable } >> > import scala.{ collection => col } >> > >> > trait MultiMap[A, B, Coll <: Addable[B, Coll] with Subtractable[B, Coll] >> > with col.Iterable[B] with col.IterableLike[B, Coll]] extends Map[A, Coll] { >> > protected def emptyContainer: Coll >> > >> > def addBinding(key: A, value: B): this.type = { >> > get(key) match { >> > case None => this(key) = emptyContainer + value >> > case Some(_) => this(key) += value >> > } >> > this >> > } >> > >> > def removeBinding(key: A, value: B): this.type = { >> > get(key) match { >> > case None => >> > case Some(_) => this(key) -= value >> > } >> > this >> > } >> > >> > def entryExists(key: A, p: B => Boolean): Boolean = get(key) match { >> > case None => false >> > case Some(values) => values exists p >> > } >> > } >> > >> > >> > ... and it goes like this. (In 2.8 add was renamed to addBinding.) >> > >> > >> > scala> import scala.collection.mutable._ >> > import scala.collection.mutable._ >> > >> > scala> val m = new HashMap[String, ListBuffer[String]] with >> > MultiMap[String, String, ListBuffer[String]] { def emptyContainer = >> > ListBuffer() } >> > m: >> > scala.collection.mutable.HashMap[String,scala.collection.mutable.ListBuffer[String]] >> > with >> > scala.collection.mutable.MultiMap[String,String,scala.collection.mutable.ListBuffer[String]] >> > = Map() >> > >> > scala> m.addBinding("values", "true") >> > res1: m.type = Map(values -> ListBuffer(true)) >> > >> > scala> m.addBinding("values", "true") >> > res2: m.type = Map(values -> ListBuffer(true, true)) >> > >> > scala> m.addBinding("values", "false") >> > res3: m.type = Map(values -> ListBuffer(true, true, false)) >> > >> > -- >> > Paul Phillips | Simplicity and elegance are unpopular because >> > Vivid | they require hard work and discipline to achieve >> > Empiricist | and education to be appreciated. >> > slap pi uphill! | -- Dijkstra >> > > > ________________________________ > Download Messenger onto your mobile for free. Learn more. |
| Free embeddable forum powered by Nabble | Forum Help |