converting an Array to a Map

classic Classic list List threaded Threaded
12 messages Options
Reply | Threaded
Open this post in threaded view
|

converting an Array to a Map

Ishaaq Chandy
Hi all,
I know how to do this in the imperative style, but no idea how to do it functionally.

Given a type Foo:
class Foo(val propKey : String, val propVal : String)

What is the most efficient way to implement this in a functional style:

def map(fooArr : Array[Foo]) : Map[String, Array[Foo]]

Where the Map is keyed by the propKey values in the Foo instances in the original array.

Thanks,
Ishaaq
Reply | Threaded
Open this post in threaded view
|

Re: converting an Array to a Map

Alex Cruise-2
Quoting Ishaaq Chandy <[hidden email]>:

> Hi all,
> I know how to do this in the imperative style, but no idea how to do it
> functionally.
>
> Given a type Foo:
> class Foo(val propKey : String, val propVal : String)
>
> What is the most efficient way to implement this in a functional style:
>
> def map(fooArr : Array[Foo]) : Map[String, Array[Foo]]

Best I've got, no doubt it can be improved substantially (maybe with  
flatMap?)  Note that I've taken the liberty of using scala.List  
instead of Array, and the resulting lists are in reverse order, but  
the algorithm doesn't use any mutable data, so I like it. :)

val foos = List(
              Foo("key1", "value1a"), Foo("key1", "value1b"),
              Foo("key2", "value2a"), Foo("key2", "value2b"),  
Foo("key2",  "value2c"),
              Foo("key3", "value3")
            )

foos.foldLeft(Map[String,List[Foo]]()){ (m, foo) =>
   val key = foo.propKey
   m + (key -> (foo :: m.getOrElse(key, Nil)))
}

yields:

Map(key1 -> List(Foo(key1,value1b), Foo(key1,value1a)),
     key2 -> List(Foo(key2,value2c), Foo(key2,value2b), Foo(key2,value2a)),
     key3 -> List(Foo(key3,value3))
)

HTH,

-0xe1a

----------------------------------------------------------------
This message was sent using IMP, the Internet Messaging Program.

Reply | Threaded
Open this post in threaded view
|

Re: converting an Array to a Map

Vlad Patryshev
In reply to this post by Ishaaq Chandy
You mean that the resulting map, for each string, as a key, should produce an array of those Foos that have the string as a key, right? And you do not want to build the actual array even when the map's get is called? Or is it okay? 

2009/5/16 Ishaaq Chandy <[hidden email]>
Hi all,
I know how to do this in the imperative style, but no idea how to do it functionally.

Given a type Foo:
class Foo(val propKey : String, val propVal : String)

What is the most efficient way to implement this in a functional style:

def map(fooArr : Array[Foo]) : Map[String, Array[Foo]]

Where the Map is keyed by the propKey values in the Foo instances in the original array.

Thanks,
Ishaaq



--
Thanks,
-Vlad
Reply | Threaded
Open this post in threaded view
|

Re: converting an Array to a Map

Ishaaq Chandy
@Vlad: Yes, to your first question. Not sure what you mean by your second question. All I'd like is for a map that returns an Option(Array) when map.get is called with a string property value.

@Alex - thanks for you answer - yes, I discovered that foldLeft does the needful a few seconds before I saw your answer. Order does not matter so I don't really care that the resultant had its lists in reverse order - though if I wanted it would be pretty simple to modify the implementation to reverse the orders at the end.

As a bonus, I'd like the implementation to be as efficient (memory and speed) as the equivalent imperative implementation - but I fear this may not be possible without mutable vars - simply because by definition appending to immutable maps and lists create new instances.

Ishaaq

2009/5/17 Vlad Patryshev <[hidden email]>
You mean that the resulting map, for each string, as a key, should produce an array of those Foos that have the string as a key, right? And you do not want to build the actual array even when the map's get is called? Or is it okay? 

2009/5/16 Ishaaq Chandy <[hidden email]>

Hi all,
I know how to do this in the imperative style, but no idea how to do it functionally.

Given a type Foo:
class Foo(val propKey : String, val propVal : String)

What is the most efficient way to implement this in a functional style:

def map(fooArr : Array[Foo]) : Map[String, Array[Foo]]

Where the Map is keyed by the propKey values in the Foo instances in the original array.

Thanks,
Ishaaq



--
Thanks,
-Vlad

Reply | Threaded
Open this post in threaded view
|

Re: converting an Array to a Map

Alex Cruise-2
Ishaaq Chandy wrote:
> @Alex - thanks for you answer - yes, I discovered that foldLeft does
> the needful a few seconds before I saw your answer. Order does not
> matter so I don't really care that the resultant had its lists in
> reverse order - though if I wanted it would be pretty simple to modify
> the implementation to reverse the orders at the end.
Yeah, or you could use a different kind of data structure--I find it's
best to try scala.List first then revisit if it's problematic.
> As a bonus, I'd like the implementation to be as efficient (memory and
> speed) as the equivalent imperative implementation - but I fear this
> may not be possible without mutable vars - simply because by
> definition appending to immutable maps and lists create new instances.
Creating new lists does create new instances, but they're fairly
efficient, because the "tail" of the new list *is* the previous one, not
a copy of it.  Not sure offhand (and too lazy to check) whether
s.c.i.HashMap makes use of that kind of technique though.

If you're confident that the collections don't escape the thread, it
probably is more efficient to use Arrays, although the allocation and
copying will start to add up if you dynamically "resize" them, or you'll
waste a lot of space if you just make them "big enough."

-0xe1a
Reply | Threaded
Open this post in threaded view
|

Re: converting an Array to a Map

Vlad Patryshev
In reply to this post by Ishaaq Chandy
But what is the efficient imperative implementation? Does not it actually depend on the distribution of keys? Besides, I am confused by the idea of returning arrays; is not a List enough? 

2009/5/16 Ishaaq Chandy <[hidden email]>
@Vlad: Yes, to your first question. Not sure what you mean by your second question. All I'd like is for a map that returns an Option(Array) when map.get is called with a string property value.

@Alex - thanks for you answer - yes, I discovered that foldLeft does the needful a few seconds before I saw your answer. Order does not matter so I don't really care that the resultant had its lists in reverse order - though if I wanted it would be pretty simple to modify the implementation to reverse the orders at the end.

As a bonus, I'd like the implementation to be as efficient (memory and speed) as the equivalent imperative implementation - but I fear this may not be possible without mutable vars - simply because by definition appending to immutable maps and lists create new instances.

Ishaaq

2009/5/17 Vlad Patryshev <[hidden email]>

You mean that the resulting map, for each string, as a key, should produce an array of those Foos that have the string as a key, right? And you do not want to build the actual array even when the map's get is called? Or is it okay? 

2009/5/16 Ishaaq Chandy <[hidden email]>

Hi all,
I know how to do this in the imperative style, but no idea how to do it functionally.

Given a type Foo:
class Foo(val propKey : String, val propVal : String)

What is the most efficient way to implement this in a functional style:

def map(fooArr : Array[Foo]) : Map[String, Array[Foo]]

Where the Map is keyed by the propKey values in the Foo instances in the original array.

Thanks,
Ishaaq



--
Thanks,
-Vlad




--
Thanks,
-Vlad
Reply | Threaded
Open this post in threaded view
|

Re: converting an Array to a Map

Ishaaq Chandy
Yes, the List is enough - the original idea was to use an Array so it could be usable by Java clients but then I realised that using a scala immutable Map defeats that purpose anyway, so I've abandoned that idea as it was a non-essential nice-to-have anyway.

2009/5/17 Vlad Patryshev <[hidden email]>
But what is the efficient imperative implementation? Does not it actually depend on the distribution of keys? Besides, I am confused by the idea of returning arrays; is not a List enough? 


2009/5/16 Ishaaq Chandy <[hidden email]>
@Vlad: Yes, to your first question. Not sure what you mean by your second question. All I'd like is for a map that returns an Option(Array) when map.get is called with a string property value.

@Alex - thanks for you answer - yes, I discovered that foldLeft does the needful a few seconds before I saw your answer. Order does not matter so I don't really care that the resultant had its lists in reverse order - though if I wanted it would be pretty simple to modify the implementation to reverse the orders at the end.

As a bonus, I'd like the implementation to be as efficient (memory and speed) as the equivalent imperative implementation - but I fear this may not be possible without mutable vars - simply because by definition appending to immutable maps and lists create new instances.

Ishaaq

2009/5/17 Vlad Patryshev <[hidden email]>

You mean that the resulting map, for each string, as a key, should produce an array of those Foos that have the string as a key, right? And you do not want to build the actual array even when the map's get is called? Or is it okay? 

2009/5/16 Ishaaq Chandy <[hidden email]>

Hi all,
I know how to do this in the imperative style, but no idea how to do it functionally.

Given a type Foo:
class Foo(val propKey : String, val propVal : String)

What is the most efficient way to implement this in a functional style:

def map(fooArr : Array[Foo]) : Map[String, Array[Foo]]

Where the Map is keyed by the propKey values in the Foo instances in the original array.

Thanks,
Ishaaq



--
Thanks,
-Vlad




--
Thanks,
-Vlad

Reply | Threaded
Open this post in threaded view
|

Re: converting an Array to a Map

Vlad Patryshev
Still, we have three options: 
  • at creation time materialize the sublists and index them lists by the keys
  • materialize them on demand, at first or on each call of get() with the appropriate key
  • never materialize them, but instead just filter the original array or list, having some kind of view (with the advantage of being able to see the changes)
I do not see yet which of these is imperative and which one is functional; I feel like it is only the way of expression that would bake it functional or imperative.


either materialize the lists, a list per key, 

2009/5/16 Ishaaq Chandy <[hidden email]>
Yes, the List is enough - the original idea was to use an Array so it could be usable by Java clients but then I realised that using a scala immutable Map defeats that purpose anyway, so I've abandoned that idea as it was a non-essential nice-to-have anyway.


2009/5/17 Vlad Patryshev <[hidden email]>
But what is the efficient imperative implementation? Does not it actually depend on the distribution of keys? Besides, I am confused by the idea of returning arrays; is not a List enough? 


2009/5/16 Ishaaq Chandy <[hidden email]>
@Vlad: Yes, to your first question. Not sure what you mean by your second question. All I'd like is for a map that returns an Option(Array) when map.get is called with a string property value.

@Alex - thanks for you answer - yes, I discovered that foldLeft does the needful a few seconds before I saw your answer. Order does not matter so I don't really care that the resultant had its lists in reverse order - though if I wanted it would be pretty simple to modify the implementation to reverse the orders at the end.

As a bonus, I'd like the implementation to be as efficient (memory and speed) as the equivalent imperative implementation - but I fear this may not be possible without mutable vars - simply because by definition appending to immutable maps and lists create new instances.

Ishaaq

2009/5/17 Vlad Patryshev <[hidden email]>

You mean that the resulting map, for each string, as a key, should produce an array of those Foos that have the string as a key, right? And you do not want to build the actual array even when the map's get is called? Or is it okay? 

2009/5/16 Ishaaq Chandy <[hidden email]>

Hi all,
I know how to do this in the imperative style, but no idea how to do it functionally.

Given a type Foo:
class Foo(val propKey : String, val propVal : String)

What is the most efficient way to implement this in a functional style:

def map(fooArr : Array[Foo]) : Map[String, Array[Foo]]

Where the Map is keyed by the propKey values in the Foo instances in the original array.

Thanks,
Ishaaq



--
Thanks,
-Vlad




--
Thanks,
-Vlad




--
Thanks,
-Vlad
Reply | Threaded
Open this post in threaded view
|

Re: converting an Array to a Map

Landei
In reply to this post by Alex Cruise-2

Arrgh wrote
Quoting Ishaaq Chandy <ishaaq@gmail.com>:

> Hi all,
> I know how to do this in the imperative style, but no idea how to do it
> functionally.
>
> Given a type Foo:
> class Foo(val propKey : String, val propVal : String)
>
> What is the most efficient way to implement this in a functional style:
>
> def map(fooArr : Array[Foo]) : Map[String, Array[Foo]]

Best I've got, no doubt it can be improved substantially (maybe with  
flatMap?)  Note that I've taken the liberty of using scala.List  
instead of Array, and the resulting lists are in reverse order, but  
the algorithm doesn't use any mutable data, so I like it. :)

val foos = List(
              Foo("key1", "value1a"), Foo("key1", "value1b"),
              Foo("key2", "value2a"), Foo("key2", "value2b"),  
Foo("key2",  "value2c"),
              Foo("key3", "value3")
            )

foos.foldLeft(Map[String,List[Foo]]()){ (m, foo) =>
   val key = foo.propKey
   m + (key -> (foo :: m.getOrElse(key, Nil)))
}

yields:

Map(key1 -> List(Foo(key1,value1b), Foo(key1,value1a)),
     key2 -> List(Foo(key2,value2c), Foo(key2,value2b), Foo(key2,value2a)),
     key3 -> List(Foo(key3,value3))
)

HTH,

-0xe1a

----------------------------------------------------------------
This message was sent using IMP, the Internet Messaging Program.
Hi,

I have no Scala at hand, so I can't try it out, but how about

val map = Map[String,List[Foo]]() ++ foos.map(_.propKey).zip(foos)

@ Scala Core Team: I think this is needed quite frequently, so how about a new method for this, e.g.

Seq[T].toMap[Key](T => Key) :Map[Key,T]

Daniel
Reply | Threaded
Open this post in threaded view
|

Re: converting an Array to a Map

Alex Boisvert-3
On Sun, May 17, 2009 at 1:26 AM, Landei <[hidden email]> wrote:

> Hi,
>
> I have no Scala at hand, so I can't try it out, but how about
>
> val map = Map[String,List[Foo]]() ++ foos.map(_.propKey).zip(foos)
>
> @ Scala Core Team: I think this is needed quite frequently, so how about a
> new method for this, e.g.
>
> Seq[T].toMap[Key](T => Key) :Map[Key,T]

Something similar was previously proposed [1] and has now landed in
trunk as Traversable[A].groupBy[K](f: A => K): Map[K, Traversable[A]].

alex

[1] http://www.nabble.com/-scala---Partitioning-an-Iterable-td23132765.html
Reply | Threaded
Open this post in threaded view
|

Re: converting an Array to a Map

Landei

Alex Boisvert-3 wrote
On Sun, May 17, 2009 at 1:26 AM, Landei <Daniel.Gronau@gmx.de> wrote:
> Hi,
>
> I have no Scala at hand, so I can't try it out, but how about
>
> val map = Map[String,List[Foo]]() ++ foos.map(_.propKey).zip(foos)
>
> @ Scala Core Team: I think this is needed quite frequently, so how about a
> new method for this, e.g.
>
> Seq[T].toMap[Key](T => Key) :Map[Key,T]

Something similar was previously proposed [1] and has now landed in
trunk as Traversable[A].groupBy[K](f: A => K): Map[K, Traversable[A]].

alex

[1] http://www.nabble.com/-scala---Partitioning-an-Iterable-td23132765.html
Thanks, good to know!

Daniel
Reply | Threaded
Open this post in threaded view
|

Re: converting an Array to a Map

Rafael de F. Ferreira-3
Landei's one liner looks great but only maps keys to Foo's, not to Array[Foo].

If scala.collection.mutable is allowed, we could make use of the
s.c.m.MultiMap trait:

 val map = (new HashMap[String,Set[Foo]] with MultiMap[String,Foo]) ++
foos.map(_.propKey).zip(foos)

By the way, why is there no MultiMap trait for immutable Maps?

--
Rafael de F. Ferreira.
http://www.rafaelferreira.net/



On Sun, May 17, 2009 at 4:54 PM, Landei <[hidden email]> wrote:

>
>
>
> Alex Boisvert-3 wrote:
>>
>> On Sun, May 17, 2009 at 1:26 AM, Landei <[hidden email]> wrote:
>>> Hi,
>>>
>>> I have no Scala at hand, so I can't try it out, but how about
>>>
>>> val map = Map[String,List[Foo]]() ++ foos.map(_.propKey).zip(foos)
>>>
>>> @ Scala Core Team: I think this is needed quite frequently, so how about
>>> a
>>> new method for this, e.g.
>>>
>>> Seq[T].toMap[Key](T => Key) :Map[Key,T]
>>
>> Something similar was previously proposed [1] and has now landed in
>> trunk as Traversable[A].groupBy[K](f: A => K): Map[K, Traversable[A]].
>>
>> alex
>>
>> [1]
>> http://www.nabble.com/-scala---Partitioning-an-Iterable-td23132765.html
>>
>>
>
> Thanks, good to know!
>
> Daniel
> --
> View this message in context: http://www.nabble.com/converting-an-Array-to-a-Map-tp23579622p23586891.html
> Sent from the Scala - User mailing list archive at Nabble.com.
>
>