Map, filter, and fold are the go to tools in a functional programmer's toolbox. They are higher order functions — that is, functions that take another function as an argument — that apply a function to a list of values in order to create a new value (either another list or an accumulated value). They largely take the place of loops and other flow control constructs that dominate imperative languages, and tend to be much safer (no chance of off-by-one errors in your loop counter, etc.) and more compact. Figuring out how to use them can take a bit of practice, though.

In this article I'm going to lightly introduce all three of these functions, and then show how they can all be implemented via fold, which for me was the bit of enlightenment that helped pull all of the concepts together.

A note on terminology

Different languages call these functions by different names. Haskell has map, filter, and two flavors of fold — foldl and foldr. In Ruby, these functions are map, select, and (confusingly!) inject. Clojure calls fold reduce. [Your favorite language] might call them something else. I'm going to use Haskell for my examples because I think the syntax is obvious enough for most people to understand even if they don't quite grok Haskell.

Map

Map is, for me, the workhorse. It takes a list of values, applies a function to each of those values, and returns a list of the result of those function applications. For example, if given a list of integers and a function that added three to whatever number it was passed, the result would be a list of integers of the same length as the original but in which each value had been incremented by three.

map (+ 3) [1,2,3,4,5]

=> [4,5,6,7,8]

Of course you can do more complex things that just add three. How about a function that takes the number, returns it if it is one, divides by two if it is even, doubles it if it is odd?

mapfx :: Int -> Int
mapfx x
  | x == 1    = 1
  | even x    = x `div` 2
  | otherwise = x * 2

map mapfx [1..10]

=> [1,1,6,2,10,3,14,4,18,5]

Here we've defined a function that does three different things depending on what argument it is passed (using guards). I think how it works is pretty obvious, but so there's no confusion, here's the same function implemented in Ruby:

def mapfx (x)
  if x == 1
    1
  elsif x.even?
    x / 2
  else
    x * 2
  end
end

Applied to a range of integers, map returns an equally long list of integers that result from the function application.

The resulting list doesn't have to be of the same type as the original list, either. This makes map useful for transforming values of one kind into values of another. For example, by mapping even over a list of integers, we get a list of booleans indicating whether or not the integer was even.

map (even) [1..10]

=> [False,True,False,True,False,True,False,True,False,True]

Filter

Filter is like map in that it applies a function to each value in a list of values, and then returns a new list. However, instead of returning a list of function results like map does, filter applies a function that returns a boolean value (a predicate), and only if the function returns true does the value get included in the return list. Thus, depending on the predicate, the resulting list of values can be anywhere from the length of the original list (if the predicate matches all the values) all the way down to an empty list (if the predicate doesn't match any of the values).

Using the previous example with filter, for example, returns a list only half as long as the original

filter (even) [1..10]

=> [2,4,6,8,10]

Because even only returns true if it is passed an even number, the result list is all even numbers.

I think of the three functions we're talking about today, filter is the easiest to understand. The predicate can be arbitrarily complex, so long as it takes one argument (the value coming out of the list of values) and returns either true or false.

Filter really shines when it is composed with other functions. For example, what is the sum of all numbers between 1 and 100,000 that are divisible by 7? Let's find out!

(sum . filter (\x -> x `mod` 7 == 0)) [1..100000]

=> 714264285

sum is a function that takes a list of numbers and sums them (we'll recreate it below when we talk about fold), returning a single result. Here the function passed to filter is created using a lambda, which is an expression that returns a function. In this case, it returns a function the returns true if x modulo 7 equals zero, and false otherwise. Tested against every number between 1 and 100,000, it results in a list of all those numbers that are evenly divisible by seven. Then sum just adds them right up.

Fold

Of the three functions we're talking about today, I think that fold is the most confusing. It is also the most powerful, though, and in a few minutes we'll see how fold can be used to implement both map and filter (and a lot of other really useful functions).

Like map and filter, fold takes a function and applies it to each of the values in a list of values in turn. What's different about fold, though, is that it also takes an accumulator, which is a value that is passed to the function along with the each value in the list. The function returns an updated accumulator, which is then passed to the next call until the list is exhausted, at which point the final accumulator is returned. This lets you operate on a list of values and build a return value piece by piece.

I think the easiest way to understand this is to look at some examples. sum and product are two Haskell functions that return the sum and product, respectively, of a list of numbers. They are perfect candidates for fold!

sum' :: (Num a) => [a] -> a
sum' xs = foldl (+) 0 xs

product' :: (Num a) => [a] -> a
product' xs = foldl (*) 1 xs

sum' [1..10]

=> 55

product' [1..10]

=> 3628800

Haskell has two different fold functions — foldl and foldr which fold from the left and right, respectively — but we'll ignore those for now and just used foldl. Let's walk through the sum' function step by step to see what's going on.

First, the accumulator and the first value in xs are passed to function (in this case, the addition function). The accumulator starts as 0, and the first value is 1. The function's return value is used as the new accumulator, so 1 + 0 equals 1, and 1 is now the accumulator. The next value down the line then gets passed to the function along with the updated accumulator, so we have 1 + 2, the result of which is the new accumulator. When we get to the end, we've added all the numbers into the accumulator, and foldl returns the final accumulator. product' works the same way, expect that its accumulator starts off at 1 (because if it was 0 then the result would always be 0, right?), and multiplies the accumulator by the value in each step until returning the final product of all of the numbers in the list.

Like map, the result of fold doesn't have to be of the same type as the list of values it was passed. As an example, let's implement two more standard functions — any, which takes a boolean function and a list of values and returns true if the function returns true when applied to any of the values, and all, which is like any but only returns true if all of the values return true when the function is applied to them.

all' :: (a -> Bool) -> [a] -> Bool
all' f xs = foldl (\acc x -> f x && acc) True xs 

any' :: (a -> Bool) -> [a] -> Bool
any' f xs = foldl (\acc x -> f x || acc) False xs

all' (even) [1..10]

=> False

all' (even) [2,4,6,8]

=> True

any' (even) [1..10]

=> True

These two functions are remarkably similar (notice the identical type signatures). In all', the starting accumulator value is True. The function is again a lambda, this time one that performs a logical AND (in Haskell, &&) on the accumulator and the result of the passed function. Because both sides of AND must be true for the result to be true, the first time the function evaluates to false the accumulator will be set to false, and all future evaluations will result in false.

any is the opposite. The starting accumulator is False, but the function used by foldl performs a logical OR (in Haskell, ||) on the accumulator and the result of the passed function. Because OR is true if one side is true, as long as at least one evaluation results in a true value, the accumulator will be true and all future evaluations will result in true.

Pretty awesome, no?

Using fold to implement map and filter

I promised at the beginning of this article that I would show examples of using fold to implement map and filter, and who am I to deceive you? While I personally would use map and filter where appropriate, and use fold for other things, it is good to show off the flexibility and power of fold. As I mentioned before, understand how fold could be used like this was the moment of enlightenment for me about exactly how it works, so hopefully it will help someone else out there grok the concept.

But first, a quick aside.

A bit about foldl, foldr, and list building

Previously I said that Haskell provides two different fold functions, foldl and foldr. Up to now I've been using foldl because there was no practical difference between the two, but there reasons the existence of foldr.

The difference between the two is pretty obvious. foldl starts on the left side of the list and goes toward the right, while foldr starts with the last, rightmost element, and goes toward the left. There are a couple of implications. One, when dealing with infinite sequences — a relatively common occurrence in lazily evaluated languages like Haskell — foldr will fail. The reason for this is obvious — it needs to find the end of the sequence to start from, and infinite sequences have no end! Seems that I didn't understand the difference between foldl and foldr as well as I thought I did. A better explanation of the difference between them can be found here — eventually I'll write a proper post going through them (once I'm sure I really understand the difference!). Until then beware some of the examples below probably should be written with foldr rather than foldl for better results.

Another implication that is relevant to what we're about to do is the order in which the original list is read, and the operator that must be used to create the resulting list in the same order as the original. In most (all?) languages that have list data structures, adding an item to the front of the list is cheap, while adding it to the end is relatively expensive. In Haskell these two operations are represented by the functions : and ++ — : takes a value and a list and returns a list with the value at the head of the list, while ++ takes a list and a value and returns a list with the value at the end of the list.

If we are building a list using foldl and we want it to be in the same order as the original list, then we have to use ++ so that each result is appended to the end. If we use foldr instead, we can use : and tack each successive result onto the front of the list. Thus, in the following examples, we're going to be using foldr.

Onto the fold-y maps and filters!

With that out of the way, let's rebuild map and filter using foldr. First, I'll show you the code, and then I'll talk through it.

map' :: (a -> b) -> [a] -> [b]
map' f xs = foldr (\x acc -> f x : acc) [] xs

filter' :: (a -> Bool) -> [a] -> [a]
filter' f xs = foldr (\x acc -> if f x then x : acc else acc) [] xs

Conceptually, these are both really simple. In previous fold examples the accumulator was a single value that was changed as a result of the passed function. In this case we are doing the same thing — the only difference is that the accumulator is a list, and at each step we're (maybe) adding a new value to the front of it.

map' is the simpler of the two. All map does is take a list, apply a function to each element in the list, and then return a list of the results. Using foldr to implement the same functionality, we start with an empty list ([]) as the accumulator, and provide a function that applies the function to an element and prepends that value to the accumulator. The result is a list of the function results, built from right to left.

filter' is more complex, but only a little bit more. filter takes a function that returns a boolean used to decide whether or not the element should be included in the final list. Here we use Haskell's if then else construct, which is equivalent to the ? : ternary operator in C and many other languages, to either return the accumulator with the element prepended, or return the accumulator without modification (thereby passing over that element). The result is a list of elements that satisfied the supplied predicate.

What's next?

I hope this has been a useful introduction to three of the most useful functions for operating on lists. There are plenty more, though! Most can be implemented with a fold and some cleverness so you don't have to learn them, but it's useful to know what's out there so that you're not reinventing the wheel one fold at a time (though reinventing the wheel can be an awesome way to learn, so go for it if you're so inclined).

Special thanks

To Miran Lipovača, the author of Learn You a Haskell for Great Good!, easily the best introductory text to Haskell out there. While I learned how these functions work when first exploring Clojure, Lipovača's descriptions are fantastic, and helped reinforce my understanding. Read it, you should.