Home » forums » LtU Forum

Reducers - A Library and Model for Collection Processing

Rich Hickey's post on Reducers - A Library and Model for Collection Processing

By adopting an alternative view of collections as reducible, rather than seqable things, we can get a complementary set of fundamental operations that tradeoff laziness for parallelism, while retaining the same high-level, functional programming model. Because the two models retain the same shape, we can easily choose whichever is appropriate for the task at hand.

By mehryar at 2012-05-08 19:18 | LtU Forum | previous forum topic | next forum topic | other blogs | 16447 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Why a neutral element?

No big surprise here, but this part makes no sense to me:

The primary signature of fold takes a combining function, a reducing function, and a collection and returns the result of combining the results of reducing subsegments of the collection, potentially in parallel. Obviously if the work is to occur in parallel, the functions must be associative, but they need not be commutative - fold preserves order. Note that there is no initial 'seed' or 'accumulator' value, as there may be with reduce and foldl. But, since the subsegments are themselves reduced (with reduce), it raises the question as to what supplies the seed values for those reductions?

The combining function (an associative binary fn) must have some 'identity' value, a value that, when combined with some X, yields X. 0 is an identity value for +, as is 1 for *. The combining fn must supply an identity value when called with no arguments (as do + and *). It will be called with no arguments to supply a seed for each leaf reduction.

If the function is associative, shouldn't we presume that any segment can be reduced independentely, that is (a # b # c # d # e) == ((a) # ((b # c) # (d # e)))?

In this case what is the use of this 'identity value' or neutral element?

By Denis Bredelet -jido at Mon, 2012-05-21 17:52 | login or register to post comments

I think it's because it

I think it's because it makes things like filter easier to implement. Suppose you have some tree structure and you filter it and then reduce it. If the filter didn't let any elements through on a particular branch, extra care would have to be taken to reduce correctly. If you have a neutral element you just put that in.

In any case you can turn an operator without a neutral element into one with a neutral element:

     x -> Some(x)
     0 -> None

     Some(x) + Some(y) = Some(x+y)
     Some(x) + None = Some(x)
     None + Some(x) = Some(x)
     None + None = None

By Jules Jacobs at Mon, 2012-05-21 19:27 | login or register to post comments

Think about what happens...

...when you pass an empty collection as an argument.

By neelk at Tue, 2012-05-22 07:46 | login or register to post comments

Still don't see the use

If you pass an empty collection, you cannot use reduce without a seed. At least with a usual implementation of reduce.

For the filter case, all you need is a boolean flag indicating if you end up with a no-element segment - no need to impose the existence of a neutral element (or use Some internally as suggested by Jules).

By Denis Bredelet -jido at Tue, 2012-05-22 18:02 | login or register to post comments