CODEWITHSUNDEEP
haskellmapreducetheory
godzsa
godzsa

Reputation: 2395

Can foldr be used as MapReduce?

I was thinking that when you do a MapReduce you are transforming your datalist and then using a reduce function to do whatever you want with the transformed data. I guess I can do the same with foldr. When doing something like foldr (filterfun . mapfun) []. Can I say that Haskell's foldr is identical to a mapreduce? Or am I missing something?

Upvotes: 0

Views: 275

Answers (1)

dfeuer
dfeuer

Reputation: 48580

Not quite. As Alec's comment indicates, foldr doesn't allow reduction to be reordered or parallelized. For example, if you have

foldr (+) 0 [1,2,3,4]

then that's

1 + (2 + (3 + 4))

The implementation of foldr can't split the container and sum each half separately, because you're just giving it a function a -> b -> b and a value b. It can't do anything with the function except apply it to both an element and an accumulator.

foldMap :: (Foldable f, Monoid m)
        => (a -> m) -> f a -> m

on the other hand, is very much a mapReduce. Since the Monoid constraint carries with it a claim of associativity, you can write a foldMap that reduces the first half of the container and the second half in parallel, and then mashes them together with <>.

The default implementation of foldr (in Data.Foldable) actually uses foldMap:

foldr c n xs = appEndo (foldMap (Endo . c) xs) n

That is, it turns each element into a function; those functions are all composed (composition forms a monoid with id as its identity) and the result applied to the seed. You can't, however, do anything useful with the intermediate functions!

Upvotes: 8

Related Questions