fold vs map

Today I learned that map can be implemented in terms of fold, i.e. if we have fold (reduce) we already have map.

The source code for foldr is:

foldr f z []     = z
foldr f z (x:xs) = f x (foldr f z xs)

So, we can do something like:

Prelude> foldr ((:).(+1)) [] [1,2,3]
[2,3,4]

Instead of using (+1) here, we can compose any function.

We can also do

Prelude> foldr (+) 0 [1,2,3]
6

The beauty of fold is that for a given data of type A, it can return data of type B.
While for map, for a given data of type A it will always return data of type A.

As we’ve shown, fold can return a list, a number, or anything else that we specify. But this is not the case with map.

The reason is that fold has a more generic morphism (catamorphism), and this is what makes it more powerful than map (homomorphism).

Here are some examples:

Prelude> foldr ((++)) [] ["hello", "world"]
"helloworld"
Prelude> foldr ((++).(words)) [] ["hello world", "I am fine"]
["hello","world","I","am","fine"]

And for something more complex:

parsePackets :: String -> [String]
parsePackets [] = []
parsePackets x = a:parsePackets b
where
(a,b) = splitAt 4 x

*Main> parsePackets "hey test 123 packets aligned in 4 bytes"
["hey ","test"," 123"," pac","kets"," ali","gned"," in ","4 by","tes"]

And here’s an analogous example with fold:

*Main> fst $ foldr (\x (chunks,partial) -> if length partial == 3 then
((x:partial):chunks,"") else (chunks,x:partial)) ([],[])
"hey test 123 packets aligned in 4 bytes"
[" tes","t 12","3 pa","cket","s al","igne","d in"," 4 b","ytes"]
Prelude> foldr (\x (chunks, partial, all, cnt) -> if x == 3 || cnt == 3 then
(x:chunks, partial, x:all, cnt+1) else (chunks, x:partial, x:all, cnt+1))
([],[],[],0) [1,2,3,4,5,6,7,3]
([3,5,3],[1,2,4,6,7],[1,2,3,4,5,6,7,3],8)

So we can notice that it is quite analogous to an imperative loop, i.e. we can look at fold’s accumulator as a local variable.

We can also implement a fixed point combinator using fold, proving that iterations can be reduced to folds:

fix f = foldr (\_ -> f) undefined (repeat undefined)

The undefined is just a gap-filler. The expression ‘repeat undefined’ generates a list of unbounded length. We don’t care about its elements, so anything will do. The fact that the list is infinite means that we get as many applications of the f parameter as we need. Note that, because the list is infinite, foldr will never reach the empty list, so it does not matter what value we give for the base case argument. Nonetheless, the type-checker requires that the argument has a polymorphic type, so it is quite convenient to use undefined here also.1

So, now we can experiment some more with recursion:


Prelude> let fix f = foldr (\_ -> f) undefined (repeat undefined)
Prelude> let fact x = if x == 0 then 1 else x * fact (x-1)
Prelude> (fix (\x -> fact)) 4
24

1. Pope, Bernie. “Getting a Fix from the Right Fold“. The Monad.Reader (6): 5–16.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s