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

[Jim Mayer]

I would also like to see the result type to be the same as the collection's
element type.

While I think it's true that one can combine map and a uniform fold function
to get a similar result (especially if one introduces intermediate objects
in the map (e.g., 'Pair')), I think it also results in more verbose, less
transparent, code.  Compare the following (I'm not up on the syntax of the
proposed collections changes, so please bear with me):

    // I like this one
    long product(List<Integer> list) {
      return list.reduce(0L, #{ sum, x -> sum * x });
    }

    or

    // I can tolerate this one
    long product(List<Integer> list) {
      return Collections.reduce(list, 0L, #{ sum, x -> sum * x });
    }

to

    // I can tolerate this one
    long product(List<Integer> list) {
      return list.map(#{x -> (long) x}).reduce(0L, #{sum, x -> sum * x});
    }

  or

    // This one makes me gag
    long product(List<Integer> list) {
      return Collections.reduce(Collections.map(list, #{x -> (long) x}), 0L,
#{sum, x -> sum * x});
    }

More fundamentally, operators like 'reduce', 'foldLeft', whatever, seem
mathematical in nature.  Most mathematical notations talk about 'integers'
or 'numbers' (or 'groups', for that matter).  They don't usually talk about
'32 bit integers' or '64 bit integers'.  Java numbers, on the other hand,
are fixed size and we can't ignore that.  To me, the first example above
clearly expresses the mathematical concept of 'product' while respecting
Java's primitive types.  In the second, though, the type conversion
implemented by the 'map' seems extraneous to the 'product' concept.

While I don't share Lawrence Kesteloot's belief that "I can genuinely see
why computer science theorists love fold-left, but it doesn't belong in any
code that will later be read
by a human", I do object to deeply nested compositions of map/reduce like
operations.

-- Jim

The second
On Mon, Mar 7, 2011 at 9:30 PM, Neal Gafter <neal at gafter.com> wrote:

> 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
>
>