Maps are Folds in Functional Programming. Here’s how:

One thing I really enjoy in programming (and in life) is when I discover a deeper truth that underpins what seem like unrelated things. There’s something spiritual about it.

I wanted to share such a discovery that I made a couple of years ago when I was new to Haskell and wanted to kill time in the Yangon International Airport.

The problem I was working on required me to filter a list into a sublist based on a function that goes through each item of a list and says if it belongs or doesn’t, by returning True or False. The method signature should look like this:

(a -> Bool) -> [a] -> [a]

(Prelude, the Haskell standard library, already has a function with this signature called filter to do this, but I wanted to see if I could implement it without it.)

To build this function the first thing I asked myself was "should I use a map or a fold?"

What is a map?

At a high level, map takes a list and return a list of the same length with each item transformed by a function:

-- given f and [a, b, c] -map-> returns [f a, f b, f c]
-- given +1 and [1, 2, 3] -map-> returns [2, 3, 4]

What is a fold?

Fold (or reduce in some languages) takes a list, and returns a single value after going through each element in a list:

-- given f, a starting value for the aggregation x, 
-- and [a, b, c] -fold-> return f c (f b (f a x))

The method signature for foldl is:

foldl :: (b -> a -> b) -> b -> [a] -> b

A simple example of a fold is adding each number in a list of numbers with an initial sum of 0. It would look like this:

To reduce a list is to fold it

What to use?!

A map returns a list of the same length and fold returns a single value. But the function we need is supposed to return something that’s in-between — a list that’s smaller than the original, but not a single value.

Then I glanced at the method signature of foldl, again:

foldl :: (b -> a -> b) -> b -> [a] -> b

Nothing here is stopping b from being a list! b is just an aggregator. What if we were building a list, instead of say, a number, in our sum example? We could just call foldl like this:

foldl (\bs a -> bs ++ [a]) [] [1, 2, 3]
-- => [1, 2, 3]

Or if we wanted to filter the list so that it doesn’t have 2’s in it:

foldl (\bs a -> if a /= 2 then bs ++ [a] else bs) [] [1, 2, 3]
-- => [1, 3]

We expressed filter, in terms of fold. Here’s a named definition of filter using a fold:

Maps are Folds

But wait! We just performed a fold that builds a list of the same size as the input list (printed again below):

foldl (\bs a -> bs ++ [a]) [] [1, 2, 3]
-- => [1, 2, 3]

That’s almost our the definition of a map!

It’s not too much more work to apply any function, f, on the item before adding it to the list. That means we go through each item of the list and create another list with the result of calling f on each item. So here is a map defined using a fold:

Moral of the story: Folds are flexible

Basically a map is just a subset of a fold with a starting value of []. Anything you’ve written with a map could have been implemented with a fold. Makes you wonder what more a fold can do…

It’s so obvious now. How did I miss this?

After seeing the textbook examples of fold like sum, I subconsciously thought of fold-ing as a piece of paper folded into something smaller. But this comparison limited my understanding of the flexibility of fold (no pun intended).

I think the real lesson here is that the metaphors our minds create to understand things can just as easily limit our understanding. Be wary!

Impressed by the way Haskell teaches, I embarked on a flight that would fold the map bringing Yangon to Bangkok. (Sorry, I had to…)