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

On Thu, Feb 11, 2010 at 11:00:51AM +0100, Ketil Malde wrote:

Johann Höchtl 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.