lambda-dev Digest, Vol 15, Issue 20 [reduce method result type]

[Neal Gafter]

On Mon, Mar 7, 2011 at 3:57 PM, Mike Duigou <mike.duigou at oracle.com> wrote:

> > From: Neal Gafter <neal at gafter.com>
> > Date: February 23, 2011 07:49:49 PST
> >
> > The "reduce" (left fold) method should not require the result type to be
> the
> > same as the collection's element type.
>
> That was my reaction as well but Brian convinced me that having a different
> result and initial type was just a conflation of map with reduce. After
> thinking about it for a while I've been unable to come up with any cases
> that couldn't be satisfied by a map step (which may merely do type
> conversion) before the reduce step. Is there another reason to have reduce
> return a different type than the element?
>

I should start by pointing out that the map/reduce formality popularized by
Google has little to do with this API, as Google's "reduce" operation
produces a collection of results.  To avoid confusion I will call Lambda's
operation "fold".

To answer your question:

First, it is strictly more expressive, as the fold function with separate
input and result types has more information to work with than either the
mapping function or the fold function in separate map/fold steps (though you
can get the same effect by introducing extra mapping steps to preserve the
needed data in intermediate types).  Second, the "initial" value in the fold
operation doesn't provide much value if the fold operation is homogeneously
typed.

Finally, there is a great deal of experience with these kinds of bulk data
APIs in the functional programming community, who after long experience have
come to prefer the version in which the source and destination types may
differ.  It would be a shame to ignore their experience and repeat mistakes
of the distant past.  See also <Graham Hutton's "A tutorial on the
universality and expressiveness of fold" from the Journal of Functional
Programming (9 (4)) <http://www.cs.nott.ac.uk/%7Egmh/fold.pdf>> and <FJ's
foldLeft operation<http://functionaljava.googlecode.com/svn/artifacts/3.0/javadoc/fj/data/List.html#foldLeft%28fj.F2,%20B%29>>
or, for some simple examples, <Matt Malone's blog post "Lots And Lots Of
foldLeft Examples"<http://oldfashionedsoftware.com/2009/07/30/lots-and-lots-of-foldleft-examples/>
>.

Being composed of experts, I expect that the Project Lambda JSR expert group
has members who are well versed in these techniques.

Cheers,
Neal