[Martijn]

Not really. There's a really nice paper by Graham Hutton, "A tutorial on the universality and expressiveness of fold" which goes into a bit more depth than OP does. Your question is answered directly in section 3.2, "The fusion property of fold". Basically, a sequence of multiple folds can be fused to a single fold.

See http://www.cs.nott.ac.uk/~gmh/fold.pdf

[carlob]

The article you linked proves the universality of fold, that I never doubted for one second.

What I was trying to say is that map is not universal, in that all function evaluations can be performed in parallel, because you can't use the result of the ith to compute the i+1th. In this respect map is in fact a restriction of fold.

[drudru11]

Awesome - I had the same question. I was basically wondering how to inform the system of the opportunity to parallelize.

BTW, Hutton's book on Haskell is just so excellent.