[Haskell-cafe] Seen on reddit: or, foldl and foldr considered slightly harmful

[Ross Paterson]

On Thu, Feb 11, 2010 at 11:00:51AM +0100, Ketil Malde wrote:
> Johann Höchtl <johann.hoechtl at gmail.com> writes:
> > In a presentation of Guy Steele for ICFP 2009 in Edinburgh:
> > http://www.vimeo.com/6624203
> > he "considers foldl and foldr" harmful as they hinder parallelism
> > because of "Process first element, then the rest" Instead he proposes
> > a divide and merge aproach, especially in the light of going parallel.
> 
> In Haskell foldl/foldr apply to linked lists (or lazy streams, if you
> prefer) which are already inherently sequential, and gets a rather harsh
> treatment.  I notice he points to finger trees, which I though was
> implemented in Data.Sequence.

Direct URL for the slides:
http://research.sun.com/projects/plrg/Publications/ICFPAugust2009Steele.pdf

As he says, associativity is the key to parallelism -- an old observation,
but still underappreciated.  Even without parallelism, associativity also
gives us greater freedom in structuring our solutions.  The moral is that
our datatypes need associative binary operations more than asymmetric ones.
We use lists too much (because they're so convenient) and apart from the
loss of parallelism it constrains our thinking to the sequential style
criticised by Backus back in 1978.

Regarding finger trees, he's just referring to the idea of caching the
results of monoidal folds in nodes of a tree.  That's crucial to the
applications of finger trees, but it can be applied to any kind of tree.
As he mentions, it's related to the Ladner-Fischer parallel prefix
algorithm, which has an upward pass accumulating sums for each subtree
followed by a downward accumulation passing each sum into the subtree
to the right.   But it's not just for parallelism: when you have these
cached values in a balanced tree, you can compute the sum of any prefix
in O(log n) steps.