This page is no longer maintained — Please continue to the home page at www.scala-lang.org

Enhancement Proposal: Make a map from set and a function, and/or create a memoizing function

22 replies
dcsobral
Joined: 2009-04-23,
User offline. Last seen 38 weeks 5 days ago.

= problem =

Out of a set of keys and a function from these keys into values, produce a map.

= analysis =

It is not uncommon the case where we want to produce a map based on a
set of keys and a function. In fact, Scala already has something
similar to it, just not for maps: tabulate. If one view sequences as
maps of indices into values, then tabulate does exactly that.

Doing this let us pre-seed maps as well as pre-compute functions that
will be applied often for a set of values.

An alternative to this need is the memoization, particularly if the
memoized inputs are available. Memoization of functions is a
particularly valuable optimization in functional programming, where
absence of side effects is strived for, if not taken for granted.

With a simple foreach, a memoizing function would have the
characteristics of the Function signature of a Map.

= enhancement alternatives =

There are three possible enhancements that may be made.

1) Create a method on Map companion, and possibly on
GenTraversableFactory as well, that takes a set and a function, and
returns either a Map or a sequence or set of tuples. In other words:

def tabulate[A, B](set: Set[A])(f: (A) => B): Map[A, B]
def tabulate[A, B](set: Set[A])(f: (A) => B): CC[(A, B)]

This could benefit from parallelization.

2) Create a method on Set, to produce maps based on a function. In other words:

def toMapWith[B](f: (A) => B): Map[A, B]

This could benefit from parallelization as well.

3) Create a MemoizingFunction extending Function, adding either or
both a constructor from Function in MemoizingFunction's companion and
a "memoize" method on Function.

One alternatve for MemoizedFunction is having the methods
memoizedInputs and isMemoizedAt.

A bolder alternative would be for MemoizingFunction to extend Map
itself, and act as a collection for the memoized input. In this case,
it would act a bit like a Map.withDefault, with the particular
difference that keys would be added whenever the default is used.

= enhancement recommendation =

While it is rather easy to create a map from a set and a function, the
code to do so, while short, hides a bit what is happening. To take two
implementations:

somesSet.foldLeft(Map[K,T]()) { (a,v) => a += (v, f(v)) }
someSet.map(x => (x, f(x))).toMap

And a parallel-broken alternative:

(someSet zip (someSet map f)).toMap

Compare that to the two suggested alternatives:

Map.tabulate(someSet)(f)
someSet toMapWith f

In addition to the readability benefits, it is a small change and in
line with pre-existing methods. If written to take advantage of ParSet
or GenSet, it may gain nice performance benefits as well.

And, of great importance, it should have little maintenance costs.

The memoizing function suggestion has a rather bigger scope, but, at
the same time, it is rather more useful as well. It needs to be
carefully written to avoid concurrency problems, which will make it
slower than a simple pre-seeded map.

The simpler implementation, extending only Function, gives most of the
benefits and should be readily understood by anyone who has worked
with languages or libraries that provide it.

The more complex implementation, extending Map as well, may be
implemented as a variation on withDefault.

For memoization, the cost of maintenance may prove a bigger drawback,
with either solution. The number of tickets on lazy certainly suggests
so, but this would be restricted to the library, and the experience
with lazy should be of help here.

On the other hand, the non triviality of providing a fast, thread-safe
memoization is an argument for doing it.

Ben Hutchison
Joined: 2009-01-21,
User offline. Last seen 42 years 45 weeks ago.
Re: Enhancement Proposal: Make a map from set and a function, a

This seem like sensible solutions to a plausible use-case. I'd welcome
any of the options you propose into the std library. My preference is
(weakly) 2, then 1, then 3.

I suspect you're not seeing much debate because its a fairly
uncontroversial improvement. File a trac request with a patch, I
reckon.

-Ben

On Sun, May 1, 2011 at 11:22 AM, Daniel Sobral wrote:
> = problem =
>
> Out of a set of keys and a function from these keys into values, produce a map.
>
> = analysis =
>
> It is not uncommon the case where we want to produce a map based on a
> set of keys and a function. In fact, Scala already has something
> similar to it, just not for maps: tabulate. If one view sequences as
> maps of indices into values, then tabulate does exactly that.
>
> Doing this let us pre-seed maps as well as pre-compute functions that
> will be applied often for a set of values.
>
> An alternative to this need is the memoization, particularly if the
> memoized inputs are available. Memoization of functions is a
> particularly valuable optimization in functional programming, where
> absence of side effects is strived for, if not taken for granted.
>
> With a simple foreach, a memoizing function would have the
> characteristics of the Function signature of a Map.
>
> = enhancement alternatives =
>
> There are three possible enhancements that may be made.
>
> 1) Create a method on Map companion, and possibly on
> GenTraversableFactory as well, that takes a set and a function, and
> returns either a Map or a sequence or set of tuples. In other words:
>
>
> def tabulate[A, B](set: Set[A])(f: (A) => B): Map[A, B]
> def tabulate[A, B](set: Set[A])(f: (A) => B): CC[(A, B)]
>
>
> This could benefit from parallelization.
>
> 2) Create a method on Set, to produce maps based on a function. In other words:
>
>
> def toMapWith[B](f: (A) => B): Map[A, B]
>
>
> This could benefit from parallelization as well.
>
> 3) Create a MemoizingFunction extending Function, adding either or
> both a constructor from Function in MemoizingFunction's companion and
> a "memoize" method on Function.
>
> One alternatve for MemoizedFunction is having the methods
> memoizedInputs and isMemoizedAt.
>
> A bolder alternative would be for MemoizingFunction to extend Map
> itself, and act as a collection for the memoized input. In this case,
> it would act a bit like a Map.withDefault, with the particular
> difference that keys would be added whenever the default is used.
>
> = enhancement recommendation =
>
> While it is rather easy to create a map from a set and a function, the
> code to do so, while short, hides a bit what is happening. To take two
> implementations:
>
>
> somesSet.foldLeft(Map[K,T]()) { (a,v) => a += (v, f(v)) }
> someSet.map(x => (x, f(x))).toMap
>
>
> And a parallel-broken alternative:
>
>
> (someSet zip (someSet map f)).toMap
>
>
> Compare that to the two suggested alternatives:
>
>
> Map.tabulate(someSet)(f)
> someSet toMapWith f
>
>
> In addition to the readability benefits, it is a small change and in
> line with pre-existing methods. If written to take advantage of ParSet
> or GenSet, it may gain nice performance benefits as well.
>
> And, of great importance, it should have little maintenance costs.
>
> The memoizing function suggestion has a rather bigger scope, but, at
> the same time, it is rather more useful as well. It needs to be
> carefully written to avoid concurrency problems, which will make it
> slower than a simple pre-seeded map.
>
> The simpler implementation, extending only Function, gives most of the
> benefits and should be readily understood by anyone who has worked
> with languages or libraries that provide it.
>
> The more complex implementation, extending Map as well, may be
> implemented as a variation on withDefault.
>
> For memoization, the cost of maintenance may prove a bigger drawback,
> with either solution. The number of tickets on lazy certainly suggests
> so, but this would be restricted to the library, and the experience
> with lazy should be of help here.
>
> On the other hand, the non triviality of providing a fast, thread-safe
> memoization is an argument for doing it.
>
> --
> Daniel C. Sobral
>
> I travel to the future all the time.
>

Kevin Wright 2
Joined: 2010-05-30,
User offline. Last seen 26 weeks 4 days ago.
Re: Enhancement Proposal: Make a map from set and a function, a
 Anyone in the UK who still hasn't figured out they need to vote "yes" on the AV referendum, this is what it's all about -->
"My preference is (weakly) 2, then 1, then 3."


--
Kevin Wright

gtalk / msn : kev [dot] lee [dot] wright [at] gmail [dot] com kev [dot] lee [dot] wright [at] gmail [dot] commail: kevin [dot] wright [at] scalatechnology [dot] com
vibe / skype: kev.lee.wrightquora: http://www.quora.com/Kevin-Wright
twitter: @thecoda

"My point today is that, if we wish to count lines of code, we should not regard them as "lines produced" but as "lines spent": the current conventional wisdom is so foolish as to book that count on the wrong side of the ledger" ~ Dijkstra
Chris Marshall
Joined: 2009-06-17,
User offline. Last seen 44 weeks 3 days ago.
RE: Enhancement Proposal: Make a map from set and a function, a
What is wrong with:
  set map (e => e -> f(e)) toMap
Or parallely:

  (set.view map (e => e -> f(e))).par toMap
Chris
> From: dcsobral [at] gmail [dot] com
> Date: Sat, 30 Apr 2011 22:22:55 -0300
> Subject: [scala-debate] Enhancement Proposal: Make a map from set and a function, and/or create a memoizing function
> To: scala-debate [at] googlegroups [dot] com
>
> = problem =
>
> Out of a set of keys and a function from these keys into values, produce a map.
>
> = analysis =
>
> It is not uncommon the case where we want to produce a map based on a
> set of keys and a function. In fact, Scala already has something
> similar to it, just not for maps: tabulate. If one view sequences as
> maps of indices into values, then tabulate does exactly that.
>
> Doing this let us pre-seed maps as well as pre-compute functions that
> will be applied often for a set of values.
>
> An alternative to this need is the memoization, particularly if the
> memoized inputs are available. Memoization of functions is a
> particularly valuable optimization in functional programming, where
> absence of side effects is strived for, if not taken for granted.
>
> With a simple foreach, a memoizing function would have the
> characteristics of the Function signature of a Map.
>
> = enhancement alternatives =
>
> There are three possible enhancements that may be made.
>
> 1) Create a method on Map companion, and possibly on
> GenTraversableFactory as well, that takes a set and a function, and
> returns either a Map or a sequence or set of tuples. In other words:
>
>
> def tabulate[A, B](set: Set[A])(f: (A) => B): Map[A, B]
> def tabulate[A, B](set: Set[A])(f: (A) => B): CC[(A, B)]
>
>
> This could benefit from parallelization.
>
> 2) Create a method on Set, to produce maps based on a function. In other words:
>
>
> def toMapWith[B](f: (A) => B): Map[A, B]
>
>
> This could benefit from parallelization as well.
>
> 3) Create a MemoizingFunction extending Function, adding either or
> both a constructor from Function in MemoizingFunction's companion and
> a "memoize" method on Function.
>
> One alternatve for MemoizedFunction is having the methods
> memoizedInputs and isMemoizedAt.
>
> A bolder alternative would be for MemoizingFunction to extend Map
> itself, and act as a collection for the memoized input. In this case,
> it would act a bit like a Map.withDefault, with the particular
> difference that keys would be added whenever the default is used.
>
> = enhancement recommendation =
>
> While it is rather easy to create a map from a set and a function, the
> code to do so, while short, hides a bit what is happening. To take two
> implementations:
>
>
> somesSet.foldLeft(Map[K,T]()) { (a,v) => a += (v, f(v)) }
> someSet.map(x => (x, f(x))).toMap
>
>
> And a parallel-broken alternative:
>
>
> (someSet zip (someSet map f)).toMap
>
>
> Compare that to the two suggested alternatives:
>
>
> Map.tabulate(someSet)(f)
> someSet toMapWith f
>
>
> In addition to the readability benefits, it is a small change and in
> line with pre-existing methods. If written to take advantage of ParSet
> or GenSet, it may gain nice performance benefits as well.
>
> And, of great importance, it should have little maintenance costs.
>
> The memoizing function suggestion has a rather bigger scope, but, at
> the same time, it is rather more useful as well. It needs to be
> carefully written to avoid concurrency problems, which will make it
> slower than a simple pre-seeded map.
>
> The simpler implementation, extending only Function, gives most of the
> benefits and should be readily understood by anyone who has worked
> with languages or libraries that provide it.
>
> The more complex implementation, extending Map as well, may be
> implemented as a variation on withDefault.
>
> For memoization, the cost of maintenance may prove a bigger drawback,
> with either solution. The number of tickets on lazy certainly suggests
> so, but this would be restricted to the library, and the experience
> with lazy should be of help here.
>
> On the other hand, the non triviality of providing a fast, thread-safe
> memoization is an argument for doing it.
>
> --
> Daniel C. Sobral
>
> I travel to the future all the time.
Ben Hutchison
Joined: 2009-01-21,
User offline. Last seen 42 years 45 weeks ago.
Re: Enhancement Proposal: Make a map from set and a function, a

On Tue, May 3, 2011 at 10:32 PM, Chris Marshall wrote:
> What is wrong with:
>   set map (e => e -> f(e)) toMap
> Or parallely:
>
>   (set.view map (e => e -> f(e))).par toMap
> Chris

...about 10 extra characters? ;)

As I think Daniel mentioned initially, this aint an earth-shattering
improvement. Its just an incremental factoring out of this recurrence.

Whether saving 10 chars is worth an extra method on the API is
questionable. To me, it is, but only just.

-Ben

>> From: dcsobral [at] gmail [dot] com
>> Date: Sat, 30 Apr 2011 22:22:55 -0300
>> Subject: [scala-debate] Enhancement Proposal: Make a map from set and a
>> function, and/or create a memoizing function
>> To: scala-debate [at] googlegroups [dot] com
>>
>> = problem =
>>
>> Out of a set of keys and a function from these keys into values, produce a
>> map.
>>
>> = analysis =
>>
>> It is not uncommon the case where we want to produce a map based on a
>> set of keys and a function. In fact, Scala already has something
>> similar to it, just not for maps: tabulate. If one view sequences as
>> maps of indices into values, then tabulate does exactly that.
>>
>> Doing this let us pre-seed maps as well as pre-compute functions that
>> will be applied often for a set of values.
>>
>> An alternative to this need is the memoization, particularly if the
>> memoized inputs are available. Memoization of functions is a
>> particularly valuable optimization in functional programming, where
>> absence of side effects is strived for, if not taken for granted.
>>
>> With a simple foreach, a memoizing function would have the
>> characteristics of the Function signature of a Map.
>>
>> = enhancement alternatives =
>>
>> There are three possible enhancements that may be made.
>>
>> 1) Create a method on Map companion, and possibly on
>> GenTraversableFactory as well, that takes a set and a function, and
>> returns either a Map or a sequence or set of tuples. In other words:
>>
>>
>> def tabulate[A, B](set: Set[A])(f: (A) => B): Map[A, B]
>> def tabulate[A, B](set: Set[A])(f: (A) => B): CC[(A, B)]
>>
>>
>> This could benefit from parallelization.
>>
>> 2) Create a method on Set, to produce maps based on a function. In other
>> words:
>>
>>
>> def toMapWith[B](f: (A) => B): Map[A, B]
>>
>>
>> This could benefit from parallelization as well.
>>
>> 3) Create a MemoizingFunction extending Function, adding either or
>> both a constructor from Function in MemoizingFunction's companion and
>> a "memoize" method on Function.
>>
>> One alternatve for MemoizedFunction is having the methods
>> memoizedInputs and isMemoizedAt.
>>
>> A bolder alternative would be for MemoizingFunction to extend Map
>> itself, and act as a collection for the memoized input. In this case,
>> it would act a bit like a Map.withDefault, with the particular
>> difference that keys would be added whenever the default is used.
>>
>> = enhancement recommendation =
>>
>> While it is rather easy to create a map from a set and a function, the
>> code to do so, while short, hides a bit what is happening. To take two
>> implementations:
>>
>>
>> somesSet.foldLeft(Map[K,T]()) { (a,v) => a += (v, f(v)) }
>> someSet.map(x => (x, f(x))).toMap
>>
>>
>> And a parallel-broken alternative:
>>
>>
>> (someSet zip (someSet map f)).toMap
>>
>>
>> Compare that to the two suggested alternatives:
>>
>>
>> Map.tabulate(someSet)(f)
>> someSet toMapWith f
>>
>>
>> In addition to the readability benefits, it is a small change and in
>> line with pre-existing methods. If written to take advantage of ParSet
>> or GenSet, it may gain nice performance benefits as well.
>>
>> And, of great importance, it should have little maintenance costs.
>>
>> The memoizing function suggestion has a rather bigger scope, but, at
>> the same time, it is rather more useful as well. It needs to be
>> carefully written to avoid concurrency problems, which will make it
>> slower than a simple pre-seeded map.
>>
>> The simpler implementation, extending only Function, gives most of the
>> benefits and should be readily understood by anyone who has worked
>> with languages or libraries that provide it.
>>
>> The more complex implementation, extending Map as well, may be
>> implemented as a variation on withDefault.
>>
>> For memoization, the cost of maintenance may prove a bigger drawback,
>> with either solution. The number of tickets on lazy certainly suggests
>> so, but this would be restricted to the library, and the experience
>> with lazy should be of help here.
>>
>> On the other hand, the non triviality of providing a fast, thread-safe
>> memoization is an argument for doing it.
>>
>> --
>> Daniel C. Sobral
>>
>> I travel to the future all the time.
>

Ivan Todoroski
Joined: 2009-05-12,
User offline. Last seen 42 years 45 weeks ago.
Re: Enhancement Proposal: Make a map from set and a function, a

On 01.05.2011 03:22, Daniel Sobral wrote:
> = problem =
>
> Out of a set of keys and a function from these keys into values, produce a map.

This looks like a common pattern, but it might be too narrow.

There is also the mirror pattern to this, which is:

Out of a set of values and a function from these values to keys, produce
a map.

To illustrate this with a mundane example, let's say you have:

class Employee(id: Int, name: String, ...)

You are presented with a list or set of these Employee objects, and you
want to create a map that indexes them by id (or some other field).

In other words, you want a Map[Int, Employee] where the keys are
Employee.id, and the values are the full Employee objects themselves.

I realize there are possible key collisions to worry about in this case
and how to handle them (e.g. by mapping objects with the same key to a
List), but it's still quite useful in some situations.

If your original pattern is encapsulated in a library method, the mirror
pattern should probably be as well.

But to be honest, both patterns are easily implemented with one-liners,
so I don't care that strongly either way.

I do like your proposal for general purpose memoization of arbitrary
Functions. Such a facility could prove to be very useful indeed for
certain algorithms, but I believe it's a slightly different question
than simply creating maps from functions, mainly because of the laziness
aspect.

Kevin Wright 2
Joined: 2010-05-30,
User offline. Last seen 26 weeks 4 days ago.
Re: Enhancement Proposal: Make a map from set and a function, a


On 3 May 2011 13:32, Chris Marshall <oxbow_lakes [at] hotmail [dot] com> wrote:
What is wrong with:
  set map (e => e -> f(e)) toMap
Or parallely:

  (set.view map (e => e -> f(e))).par toMap
Chris

I'd love if we could write something like:
   set.par.zipWith(f).toMap
All that's missing is the zipWith method, though I guess it's not *too* hard to add with a pimp...
 
> From: dcsobral [at] gmail [dot] com
> Date: Sat, 30 Apr 2011 22:22:55 -0300
> Subject: [scala-debate] Enhancement Proposal: Make a map from set and a function, and/or create a memoizing function
> To: scala-debate [at] googlegroups [dot] com
>
> = problem =
>
> Out of a set of keys and a function from these keys into values, produce a map.
>
> = analysis =
>
> It is not uncommon the case where we want to produce a map based on a
> set of keys and a function. In fact, Scala already has something
> similar to it, just not for maps: tabulate. If one view sequences as
> maps of indices into values, then tabulate does exactly that.
>
> Doing this let us pre-seed maps as well as pre-compute functions that
> will be applied often for a set of values.
>
> An alternative to this need is the memoization, particularly if the
> memoized inputs are available. Memoization of functions is a
> particularly valuable optimization in functional programming, where
> absence of side effects is strived for, if not taken for granted.
>
> With a simple foreach, a memoizing function would have the
> characteristics of the Function signature of a Map.
>
> = enhancement alternatives =
>
> There are three possible enhancements that may be made.
>
> 1) Create a method on Map companion, and possibly on
> GenTraversableFactory as well, that takes a set and a function, and
> returns either a Map or a sequence or set of tuples. In other words:
>
>
> def tabulate[A, B](set: Set[A])(f: (A) => B): Map[A, B]
> def tabulate[A, B](set: Set[A])(f: (A) => B): CC[(A, B)]
>
>
> This could benefit from parallelization.
>
> 2) Create a method on Set, to produce maps based on a function. In other words:
>
>
> def toMapWith[B](f: (A) => B): Map[A, B]
>
>
> This could benefit from parallelization as well.
>
> 3) Create a MemoizingFunction extending Function, adding either or
> both a constructor from Function in MemoizingFunction's companion and
> a "memoize" method on Function.
>
> One alternatve for MemoizedFunction is having the methods
> memoizedInputs and isMemoizedAt.
>
> A bolder alternative would be for MemoizingFunction to extend Map
> itself, and act as a collection for the memoized input. In this case,
> it would act a bit like a Map.withDefault, with the particular
> difference that keys would be added whenever the default is used.
>
> = enhancement recommendation =
>
> While it is rather easy to create a map from a set and a function, the
> code to do so, while short, hides a bit what is happening. To take two
> implementations:
>
>
> somesSet.foldLeft(Map[K,T]()) { (a,v) => a += (v, f(v)) }
> someSet.map(x => (x, f(x))).toMap
>
>
> And a parallel-broken alternative:
>
>
> (someSet zip (someSet map f)).toMap
>
>
> Compare that to the two suggested alternatives:
>
>
> Map.tabulate(someSet)(f)
> someSet toMapWith f
>
>
> In addition to the readability benefits, it is a small change and in
> line with pre-existing methods. If written to take advantage of ParSet
> or GenSet, it may gain nice performance benefits as well.
>
> And, of great importance, it should have little maintenance costs.
>
> The memoizing function suggestion has a rather bigger scope, but, at
> the same time, it is rather more useful as well. It needs to be
> carefully written to avoid concurrency problems, which will make it
> slower than a simple pre-seeded map.
>
> The simpler implementation, extending only Function, gives most of the
> benefits and should be readily understood by anyone who has worked
> with languages or libraries that provide it.
>
> The more complex implementation, extending Map as well, may be
> implemented as a variation on withDefault.
>
> For memoization, the cost of maintenance may prove a bigger drawback,
> with either solution. The number of tickets on lazy certainly suggests
> so, but this would be restricted to the library, and the experience
> with lazy should be of help here.
>
> On the other hand, the non triviality of providing a fast, thread-safe
> memoization is an argument for doing it.
>
> --
> Daniel C. Sobral
>
> I travel to the future all the time.



--
Kevin Wright

gtalk / msn : kev [dot] lee [dot] wright [at] gmail [dot] comkev [dot] lee [dot] wright [at] gmail [dot] commail: kevin [dot] wright [at] scalatechnology [dot] com
vibe / skype: kev.lee.wrightquora: http://www.quora.com/Kevin-Wright
twitter: @thecoda

"My point today is that, if we wish to count lines of code, we should not regard them as "lines produced" but as "lines spent": the current conventional wisdom is so foolish as to book that count on the wrong side of the ledger" ~ Dijkstra
Randall R Schulz
Joined: 2008-12-16,
User offline. Last seen 1 year 29 weeks ago.
Re: Enhancement Proposal: Make a map from set and a function, a

On Tuesday May 3 2011, Kevin Wright wrote:
> On 3 May 2011 13:32, Chris Marshall wrote:
> > What is wrong with:
> >
> > set map (e => e -> f(e)) toMap
> >
> > Or parallely:
> >
> > (set.view map (e => e -> f(e))).par toMap
> >
> > Chris
>
> I'd love if we could write something like:
>
> set.par.zipWith(f).toMap

I hate to bring it up, but "with" is poorly chosen for what this method
does. It does not zip the values "with f." That would mean pairing each
value in set with f, not the result of applying f to those values.

zipUsing or zipApplying would be better, in my opinion.

> All that's missing is the zipWith method, though I guess it's not
> *too* hard to add with a pimp...
>
> ...

Randall Schulz

Kevin Wright 2
Joined: 2010-05-30,
User offline. Last seen 26 weeks 4 days ago.
Re: Enhancement Proposal: Make a map from set and a function, a


On 3 May 2011 13:56, Ivan Todoroski <grnch_lists [at] gmx [dot] net> wrote:
On 01.05.2011 03:22, Daniel Sobral wrote:
= problem =

Out of a set of keys and a function from these keys into values, produce a map.

This looks like a common pattern, but it might be too narrow.

There is also the mirror pattern to this, which is:

Out of a set of values and a function from these values to keys, produce a map.


Not entirely right, your approach is *still* too narrow.
Maps are restricted to having unique keys, whereas an input sequence may have duplicate entries which you want retained in the output.  This becomes even more significant if you consider that the mapping function could well have relevant side-effects (usually a deplorable practice, but not technically illegal, so we have to allow for it).
As per my musings on zipWith (which, yes, I know is less than perfect as names go), a better solution is to map each element of the input to a pair containing that element and the output of the mapping function, it's then trivial to call `.toMap` on this result if that's what you really need.
 
To illustrate this with a mundane example, let's say you have:

class Employee(id: Int, name: String, ...)

You are presented with a list or set of these Employee objects, and you want to create a map that indexes them by id (or some other field).

In other words, you want a Map[Int, Employee] where the keys are Employee.id, and the values are the full Employee objects themselves.

I realize there are possible key collisions to worry about in this case and how to handle them (e.g. by mapping objects with the same key to a List), but it's still quite useful in some situations.

If your original pattern is encapsulated in a library method, the mirror pattern should probably be as well.

But to be honest, both patterns are easily implemented with one-liners, so I don't care that strongly either way.

I do like your proposal for general purpose memoization of arbitrary Functions. Such a facility could prove to be very useful indeed for certain algorithms, but I believe it's a slightly different question than simply creating maps from functions, mainly because of the laziness aspect.



--
Kevin Wright

gtalk / msn : kev [dot] lee [dot] wright [at] gmail [dot] comkev [dot] lee [dot] wright [at] gmail [dot] commail: kevin [dot] wright [at] scalatechnology [dot] com
vibe / skype: kev.lee.wrightquora: http://www.quora.com/Kevin-Wright
twitter: @thecoda

"My point today is that, if we wish to count lines of code, we should not regard them as "lines produced" but as "lines spent": the current conventional wisdom is so foolish as to book that count on the wrong side of the ledger" ~ Dijkstra
dcsobral
Joined: 2009-04-23,
User offline. Last seen 38 weeks 5 days ago.
Re: Enhancement Proposal: Make a map from set and a function, a

Consider tabulate:

Seq.tabulate(10)(x => x * 2)
(0 until 10).toSeq map (x => x * 2)

It is not so much a matter of characters, as it is a matter of naming
a pattern. So the problem with map -- or with zipWith, which I think
is worthwhile entirely on its own -- is that it isn't narrow enough.

But, of course, hearing what others think is the whole point of
posting this to debate.

On Tue, May 3, 2011 at 09:32, Chris Marshall wrote:
> What is wrong with:
>   set map (e => e -> f(e)) toMap
> Or parallely:
>
>   (set.view map (e => e -> f(e))).par toMap
> Chris
>> From: dcsobral [at] gmail [dot] com
>> Date: Sat, 30 Apr 2011 22:22:55 -0300
>> Subject: [scala-debate] Enhancement Proposal: Make a map from set and a
>> function, and/or create a memoizing function
>> To: scala-debate [at] googlegroups [dot] com
>>
>> = problem =
>>
>> Out of a set of keys and a function from these keys into values, produce a
>> map.
>>
>> = analysis =
>>
>> It is not uncommon the case where we want to produce a map based on a
>> set of keys and a function. In fact, Scala already has something
>> similar to it, just not for maps: tabulate. If one view sequences as
>> maps of indices into values, then tabulate does exactly that.
>>
>> Doing this let us pre-seed maps as well as pre-compute functions that
>> will be applied often for a set of values.
>>
>> An alternative to this need is the memoization, particularly if the
>> memoized inputs are available. Memoization of functions is a
>> particularly valuable optimization in functional programming, where
>> absence of side effects is strived for, if not taken for granted.
>>
>> With a simple foreach, a memoizing function would have the
>> characteristics of the Function signature of a Map.
>>
>> = enhancement alternatives =
>>
>> There are three possible enhancements that may be made.
>>
>> 1) Create a method on Map companion, and possibly on
>> GenTraversableFactory as well, that takes a set and a function, and
>> returns either a Map or a sequence or set of tuples. In other words:
>>
>>
>> def tabulate[A, B](set: Set[A])(f: (A) => B): Map[A, B]
>> def tabulate[A, B](set: Set[A])(f: (A) => B): CC[(A, B)]
>>
>>
>> This could benefit from parallelization.
>>
>> 2) Create a method on Set, to produce maps based on a function. In other
>> words:
>>
>>
>> def toMapWith[B](f: (A) => B): Map[A, B]
>>
>>
>> This could benefit from parallelization as well.
>>
>> 3) Create a MemoizingFunction extending Function, adding either or
>> both a constructor from Function in MemoizingFunction's companion and
>> a "memoize" method on Function.
>>
>> One alternatve for MemoizedFunction is having the methods
>> memoizedInputs and isMemoizedAt.
>>
>> A bolder alternative would be for MemoizingFunction to extend Map
>> itself, and act as a collection for the memoized input. In this case,
>> it would act a bit like a Map.withDefault, with the particular
>> difference that keys would be added whenever the default is used.
>>
>> = enhancement recommendation =
>>
>> While it is rather easy to create a map from a set and a function, the
>> code to do so, while short, hides a bit what is happening. To take two
>> implementations:
>>
>>
>> somesSet.foldLeft(Map[K,T]()) { (a,v) => a += (v, f(v)) }
>> someSet.map(x => (x, f(x))).toMap
>>
>>
>> And a parallel-broken alternative:
>>
>>
>> (someSet zip (someSet map f)).toMap
>>
>>
>> Compare that to the two suggested alternatives:
>>
>>
>> Map.tabulate(someSet)(f)
>> someSet toMapWith f
>>
>>
>> In addition to the readability benefits, it is a small change and in
>> line with pre-existing methods. If written to take advantage of ParSet
>> or GenSet, it may gain nice performance benefits as well.
>>
>> And, of great importance, it should have little maintenance costs.
>>
>> The memoizing function suggestion has a rather bigger scope, but, at
>> the same time, it is rather more useful as well. It needs to be
>> carefully written to avoid concurrency problems, which will make it
>> slower than a simple pre-seeded map.
>>
>> The simpler implementation, extending only Function, gives most of the
>> benefits and should be readily understood by anyone who has worked
>> with languages or libraries that provide it.
>>
>> The more complex implementation, extending Map as well, may be
>> implemented as a variation on withDefault.
>>
>> For memoization, the cost of maintenance may prove a bigger drawback,
>> with either solution. The number of tickets on lazy certainly suggests
>> so, but this would be restricted to the library, and the experience
>> with lazy should be of help here.
>>
>> On the other hand, the non triviality of providing a fast, thread-safe
>> memoization is an argument for doing it.
>>
>> --
>> Daniel C. Sobral
>>
>> I travel to the future all the time.
>

Chris Marshall
Joined: 2009-06-17,
User offline. Last seen 44 weeks 3 days ago.
RE: Enhancement Proposal: Make a map from set and a function, a
zipBy? zipUsing?
I agree that this is much nicer. I had my own enhancement request (calling the function "mapTo") refused: https://lampsvn.epfl.ch/trac/scala/ticket/2605 on the grounds that it was unnecessary. Only to see later that nonEmpty was added to the collections!
Chris

Date: Tue, 3 May 2011 13:49:59 +0100
Subject: Re: [scala-debate] Enhancement Proposal: Make a map from set and a function, and/or create a memoizing function
From: kev [dot] lee [dot] wright [at] gmail [dot] com
To: oxbow_lakes [at] hotmail [dot] com
CC: scala-debate [at] googlegroups [dot] com



On 3 May 2011 13:32, Chris Marshall <oxbow_lakes [at] hotmail [dot] com> wrote:
What is wrong with:
  set map (e => e -> f(e)) toMap
Or parallely:

  (set.view map (e => e -> f(e))).par toMap
Chris

I'd love if we could write something like:
   set.par.zipWith(f).toMap

Kevin Wright 2
Joined: 2010-05-30,
User offline. Last seen 26 weeks 4 days ago.
Re: Enhancement Proposal: Make a map from set and a function, a
autoZip?

On 3 May 2011 18:44, Chris Marshall <oxbow_lakes [at] hotmail [dot] com> wrote:
zipBy? zipUsing?
I agree that this is much nicer. I had my own enhancement request (calling the function "mapTo") refused: https://lampsvn.epfl.ch/trac/scala/ticket/2605 on the grounds that it was unnecessary. Only to see later that nonEmpty was added to the collections!
Chris

Date: Tue, 3 May 2011 13:49:59 +0100
Subject: Re: [scala-debate] Enhancement Proposal: Make a map from set and a function, and/or create a memoizing function
From: kev [dot] lee [dot] wright [at] gmail [dot] com
To: oxbow_lakes [at] hotmail [dot] com
CC: scala-debate [at] googlegroups [dot] com



On 3 May 2011 13:32, Chris Marshall <oxbow_lakes [at] hotmail [dot] com> wrote:
What is wrong with:
  set map (e => e -> f(e)) toMap
Or parallely:

  (set.view map (e => e -> f(e))).par toMap
Chris

I'd love if we could write something like:
   set.par.zipWith(f).toMap




--
Kevin Wright

gtalk / msn : kev [dot] lee [dot] wright [at] gmail [dot] comkev [dot] lee [dot] wright [at] gmail [dot] commail: kevin [dot] wright [at] scalatechnology [dot] com
vibe / skype: kev.lee.wrightquora: http://www.quora.com/Kevin-Wright
twitter: @thecoda

"My point today is that, if we wish to count lines of code, we should not regard them as "lines produced" but as "lines spent": the current conventional wisdom is so foolish as to book that count on the wrong side of the ledger" ~ Dijkstra
extempore
Joined: 2008-12-17,
User offline. Last seen 35 weeks 3 days ago.
Re: Enhancement Proposal: Make a map from set and a function, a

On 5/3/11 10:44 AM, Chris Marshall wrote:
> I agree that this is much nicer. I had my own enhancement request
> (calling the function "mapTo")
> refused: https://lampsvn.epfl.ch/trac/scala/ticket/2605 on the grounds
> that it was unnecessary. Only to see later that nonEmpty was added to
> the collections!

Look, I agree with you that this map function is needed and I would use
it all the time, but give it a rest about nonEmpty and your whole "my
good idea was given the shaft while these trivialities were implemented
instead" shtick. There's no conspiracy.

Kevin Wright 2
Joined: 2010-05-30,
User offline. Last seen 26 weeks 4 days ago.
Re: Enhancement Proposal: Make a map from set and a function, a
A list of suggestions:
autoZipautoZipWithendoZipendoZipWithfzipmapZip zipAgainstzipApplyingzipByzipf zipMapzipTozipUsingzipWith
Following the convention of withFilter and sortWith (also the deprecated equalsWith) methods that all take a lambda, I'm still very much in favour of a name that ends with "With"
Any more ideas?


On 3 May 2011 18:48, Paul Phillips <paulp [at] improving [dot] org> wrote:
On 5/3/11 10:44 AM, Chris Marshall wrote:
> I agree that this is much nicer. I had my own enhancement request
> (calling the function "mapTo")
> refused: https://lampsvn.epfl.ch/trac/scala/ticket/2605 on the grounds
> that it was unnecessary. Only to see later that nonEmpty was added to
> the collections!

Look, I agree with you that this map function is needed and I would use
it all the time, but give it a rest about nonEmpty and your whole "my
good idea was given the shaft while these trivialities were implemented
instead" shtick.  There's no conspiracy.



--
Kevin Wright

gtalk / msn : kev [dot] lee [dot] wright [at] gmail [dot] comkev [dot] lee [dot] wright [at] gmail [dot] commail: kevin [dot] wright [at] scalatechnology [dot] com
vibe / skype: kev.lee.wrightquora: http://www.quora.com/Kevin-Wright
twitter: @thecoda

"My point today is that, if we wish to count lines of code, we should not regard them as "lines produced" but as "lines spent": the current conventional wisdom is so foolish as to book that count on the wrong side of the ledger" ~ Dijkstra
Chris Marshall
Joined: 2009-06-17,
User offline. Last seen 44 weeks 3 days ago.
RE: Enhancement Proposal: Make a map from set and a function, a
Sorry, I just couldn't resist. For the record, I *like* nonEmpty. So much, in fact, I use !nonEmpty to test for emptiness

> Date: Tue, 3 May 2011 10:48:11 -0700
> From: paulp [at] improving [dot] org
>> Look, I agree with you that this map function is needed and I would use
> it all the time, but give it a rest about nonEmpty and your whole "my
> good idea was given the shaft while these trivialities were implemented
> instead" shtick. There's no conspiracy.
Tony Morris 2
Joined: 2009-03-20,
User offline. Last seen 42 years 45 weeks ago.
Re: Enhancement Proposal: Make a map from set and a function, a

On 04/05/11 03:48, Paul Phillips wrote:
> On 5/3/11 10:44 AM, Chris Marshall wrote:
>> I agree that this is much nicer. I had my own enhancement request
>> (calling the function "mapTo")
>> refused: https://lampsvn.epfl.ch/trac/scala/ticket/2605 on the grounds
>> that it was unnecessary. Only to see later that nonEmpty was added to
>> the collections!
> Look, I agree with you that this map function is needed and I would use
> it all the time, but give it a rest about nonEmpty and your whole "my
> good idea was given the shaft while these trivialities were implemented
> instead" shtick. There's no conspiracy.
FWIW, I agree, conspiracy is not a consistent explanation.

Naftoli Gugenheim
Joined: 2008-12-17,
User offline. Last seen 42 years 45 weeks ago.
Re: Enhancement Proposal: Make a map from set and a function, a


On Tue, May 3, 2011 at 8:56 AM, Ivan Todoroski <grnch_lists [at] gmx [dot] net> wrote:
Out of a set of values and a function from these values to keys, produce a map.


Isn't that what groupBy does?
extempore
Joined: 2008-12-17,
User offline. Last seen 35 weeks 3 days ago.
Re: Enhancement Proposal: Make a map from set and a function, a

On 5/4/11 4:18 PM, Naftoli Gugenheim wrote:
> Out of a set of values and a function from these values to keys,
> produce a map.
>
> Isn't that what groupBy does?

groupBy takes CC[A] and A => B and creates Map[B, CC[A]].

The function being requested takes CC[A] and A => B and produces Map[A, B].

These are only similar inasmuch as both make maps.

Alex Cruise
Joined: 2008-12-17,
User offline. Last seen 2 years 26 weeks ago.
Re: Enhancement Proposal: Make a map from set and a function, a
On Wed, May 4, 2011 at 4:37 PM, Paul Phillips <paulp [at] improving [dot] org> wrote:
On 5/4/11 4:18 PM, Naftoli Gugenheim wrote:
>     Out of a set of values and a function from these values to keys,
>     produce a map.
>
> Isn't that what groupBy does?

groupBy takes CC[A] and A => B and creates Map[B, CC[A]].

The function being requested takes CC[A] and A => B and produces Map[A, B].

These are only similar inasmuch as both make maps.

Just to add to this menagerie of creatures real and hypothetical, I'm fond of what I like to call groupBy2:
  /**
   * Like {@link scala.collection.Traversable#groupBy} but lets you return both the key and the value for the resulting
   * Map-of-Lists, rather than just the key.
   *
   * @param in the input list
   * @param f the function that maps A's in the input list to a (K,V) tuple for the output map.
   * @tparam A the type of elements in the source list
   * @tparam K the type of the first element of the tuple returned by the function; will be used as keys for the result
   * @tparam V the type of the second element of the tuple returned by the function; will be used as values for the result
   * @return a Map-of-Lists
   */
  def groupBy2[A,K,V](in: List[A])(f: PartialFunction[A,(K,V)]): Map[K,List[V]] = {
    def _groupBy2[A, K, V](in: List[A],
                          got: Map[K, List[V]],
                            f: PartialFunction[A, (K, V)])
                             : Map[K, List[V]] =
    in match {
      case Nil =>
        got.map {case (k, vs) => (k, vs.reverse)}
      case x :: xs if f.isDefinedAt(x) =>
        val (b, c) = f(x)
        val appendTo = got.getOrElse(b, Nil)
        _groupBy2(xs, got.updated(b, c :: appendTo), f)
      case x :: xs =>
        _groupBy2(xs, got, f)
    }
    _groupBy2(in, Map.empty, f)
  }
 -0xe1a
Ivan Todoroski
Joined: 2009-05-12,
User offline. Last seen 42 years 45 weeks ago.
Re: Enhancement Proposal: Make a map from set and a function, a

On 05.05.2011 01:37, Paul Phillips wrote:
> On 5/4/11 4:18 PM, Naftoli Gugenheim wrote:
>> Out of a set of values and a function from these values to keys,
>> produce a map.
>>
>> Isn't that what groupBy does?
>
> groupBy takes CC[A] and A => B and creates Map[B, CC[A]].
>
> The function being requested takes CC[A] and A => B and produces Map[A, B].
>
> These are only similar inasmuch as both make maps.

Actually, Naftoli is right.

Daniel's original use case at the start of the thread was as you said:

Function that takes CC[A] and A=>B and produces Map[A,B].

My "mirror" use case was:

Function that takes CC[A] and A=>B and produces Map[B,A].

(or it could produce Map[B,CC[A]] in order to handle duplicate keys
properly).

As Naftoli correctly observed, my "mirror" use case is pretty much
covered by groupBy(). I should learn the Scala library better.

Sorry again for the noise, I guess I should be quiet when the grown-ups
are talking. :)

Ivan Todoroski
Joined: 2009-05-12,
User offline. Last seen 42 years 45 weeks ago.
Re: Enhancement Proposal: Make a map from set and a function, a

On 05.05.2011 01:18, Naftoli Gugenheim wrote:
> On Tue, May 3, 2011 at 8:56 AM, Ivan Todoroski wrote:
>
> Out of a set of values and a function from these values to keys,
> produce a map.
>
>
> Isn't that what groupBy does?

Huh, you're right. I really need to get around to studying the new
collections in detail. This method even handles duplicate keys by
storing the original objects in buckets.

I guess you can ignore the sub-thread started by me, my use case is
already covered. Sorry for the noise.

Chris Marshall
Joined: 2009-06-17,
User offline. Last seen 44 weeks 3 days ago.
RE: Enhancement Proposal: Make a map from set and a function, a
From my enhancement request (https://lampsvn.epfl.ch/trac/scala/ticket/2604), I called this function "mapBy".
Perhaps it should be zipBy (mapTo) and zippedBy (mapBy)
Chris

> Date: Thu, 5 May 2011 12:07:13 +0200
> From: grnch_lists [at] gmx [dot] net
> To: paulp [at] improving [dot] org
> CC: naftoligug [at] gmail [dot] com; dcsobral [at] gmail [dot] com; scala-debate [at] googlegroups [dot] com
> Subject: Re: [scala-debate] Enhancement Proposal: Make a map from set and a function, and/or create a memoizing function
>
> On 05.05.2011 01:37, Paul Phillips wrote:
> > On 5/4/11 4:18 PM, Naftoli Gugenheim wrote:
> >> Out of a set of values and a function from these values to keys,
> >> produce a map.
> >>
> >> Isn't that what groupBy does?
> >
> > groupBy takes CC[A] and A => B and creates Map[B, CC[A]].
> >
> > The function being requested takes CC[A] and A => B and produces Map[A, B].
> >
> > These are only similar inasmuch as both make maps.
>
> Actually, Naftoli is right.
>
> Daniel's original use case at the start of the thread was as you said:
>
> Function that takes CC[A] and A=>B and produces Map[A,B].
>
> My "mirror" use case was:
>
> Function that takes CC[A] and A=>B and produces Map[B,A].
>
> (or it could produce Map[B,CC[A]] in order to handle duplicate keys
> properly).
>
> As Naftoli correctly observed, my "mirror" use case is pretty much
> covered by groupBy(). I should learn the Scala library better.
>
> Sorry again for the noise, I guess I should be quiet when the grown-ups
> are talking. :)
Ruediger Keller 2
Joined: 2010-04-30,
User offline. Last seen 42 years 45 weeks ago.
Re: Enhancement Proposal: Make a map from set and a function, a

While we are debating additions to the collection methods:

What happened to the symmetric twins of takeWhile and dropWhile:
takeRightWhile and dropRightWhile? As we have takeRight and dropRight,
I figured we might want these, too.
Regards,
Rüdiger

2011/5/5 Chris Marshall :
> From my enhancement request
> (https://lampsvn.epfl.ch/trac/scala/ticket/2604), I called this function
> "mapBy".
> Perhaps it should be zipBy (mapTo) and zippedBy (mapBy)
> Chris
>
>> Date: Thu, 5 May 2011 12:07:13 +0200
>> From: grnch_lists [at] gmx [dot] net
>> To: paulp [at] improving [dot] org
>> CC: naftoligug [at] gmail [dot] com; dcsobral [at] gmail [dot] com;
>> scala-debate [at] googlegroups [dot] com
>> Subject: Re: [scala-debate] Enhancement Proposal: Make a map from set and
>> a function, and/or create a memoizing function
>>
>> On 05.05.2011 01:37, Paul Phillips wrote:
>> > On 5/4/11 4:18 PM, Naftoli Gugenheim wrote:
>> >> Out of a set of values and a function from these values to keys,
>> >> produce a map.
>> >>
>> >> Isn't that what groupBy does?
>> >
>> > groupBy takes CC[A] and A => B and creates Map[B, CC[A]].
>> >
>> > The function being requested takes CC[A] and A => B and produces Map[A,
>> > B].
>> >
>> > These are only similar inasmuch as both make maps.
>>
>> Actually, Naftoli is right.
>>
>> Daniel's original use case at the start of the thread was as you said:
>>
>> Function that takes CC[A] and A=>B and produces Map[A,B].
>>
>> My "mirror" use case was:
>>
>> Function that takes CC[A] and A=>B and produces Map[B,A].
>>
>> (or it could produce Map[B,CC[A]] in order to handle duplicate keys
>> properly).
>>
>> As Naftoli correctly observed, my "mirror" use case is pretty much
>> covered by groupBy(). I should learn the Scala library better.
>>
>> Sorry again for the noise, I guess I should be quiet when the grown-ups
>> are talking. :)
>

Copyright © 2012 École Polytechnique Fédérale de Lausanne (EPFL), Lausanne, Switzerland