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

Jan-Willem Maessen jmaessen at alum.mit.edu
Thu Feb 11 10:21:42 EST 2010

On Feb 11, 2010, at 3:41 AM, Johann Höchtl wrote:

> 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.
> The slides at
> http://docs.google.com/viewer?url=http%3A%2F%2Fresearch.sun.com%2Fprojects%2Fplrg%2FPublications%2FICFPAugust2009Steele.pdf
> [Bware: Google docs]

There's no need to use Google docs.  A direct url for the pdf:


I recently gave a followup talk at Portland State, arguing that notation matters, and that even with better notation programmer mindset is also going to be hard to change:


The key thing here isn't *just* the handedness of lists, but the handedness of foldl/foldr *irrespective of the underlying data structure*.  So switching to tree-structured data a la fingertrees is a necessary step, but not a sufficient one.  The use of monoidal reductions has always been an important part of parallel programming.

> are somewhat  geared towards Fortress, but I wonder what Haskellers
> have to say about his position.

Now, what if list comprehensions were really shorthand for construction of Applicative or Monoid structures by traversing a mixture of data types with a common interface (something like this one)?

class Generator t e | t -> e
    mapReduce :: (Monoid m) => t -> (e -> m) -> m

-Jan-Willem Maessen
 Another Fortress/Haskell crossover

> Greetings,
>   Johann
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe

More information about the Haskell-Cafe mailing list