[grav1tas]

I think it might be important to note that while the terms map and reduce do come from Lisp, they're not one-to-one with what these functions do in Lisp. The original MapReduce paper mentions the borrowing, but doesn't really go into specifics. There's a good paper by Ralf Lämmel that describes the relation that MapReduce has to "map" and "reduce" at http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.104.... . I liked this paper much better and found it the most informative functional explanation to MapReduce (note, it's in Haskell).

I think MapReduce is really part of a more general pattern where you have an (in more Haskell-y terms) unfold (anamorphism) to a foldr (catamorphism). If your operations on the items in your intermediate set of data in the MapReduce are associative/commutative, you can work out parallelization more or less for free. It's pretty cool stuff, and really not that complicated when you sit down and think about it.

[Dn_Ab]

Wow. Thank you. I wish I could upvote you more. I have never looked into Google's "MapReduce" but if what you say is true then my assumptions on it were completely wrong. I assumed it was 1-1 with map and reduce. But if it is generating a set of unfolds into 'essentially' fold (is it? I only skimmed the first pages due to time) then that is a very important detail and makes the name a bit of a misnomer. Why don't people make a bigger deal about this - unfold, fold is not harder but it requires a different mindset and approach than map fold.

If you are approaching it thinking it is just a map and fold then you are going in disadvantaged and will have to unlearn that fact to properly leverage something that is actually even more impressive/useful/powerful than a mare fold o map.