Higher Order Functions and the Big Three

Previously, we saw how some programming languages allowed us to treat functions exactly the same as objects. With this concept in mind, we implemented functions that received one or more functions as input arguments and functions that returned another function as an output. These can be categorized as higher order functions.

While higher order and first-class functions are related, the former is characterizing some mathematical property of a function, while the latter is describing an implementation detail for functions in a given programming language. Although in the context of computer code, it would be hard to imagine one without the other.

So what are the higher order functions you’ll actually reach for on a daily basis? There are three that show up constantly. In functional programming circles, they’re so fundamental that knowing them is basically table stakes: map, filter, and fold.

Map

map takes a function and a list, applies the function to every element, and returns the new list. That’s it. No surprises.

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

map (*2) [1, 2, 3, 4, 5]
-- [2, 4, 6, 8, 10]

map show [1, 2, 3]
-- ["1", "2", "3"]

The type signature tells the whole story: give me a function from a to b, and a list of as, and I’ll give you a list of bs. Notice that the input and output element types don’t have to match. You can map a list of integers into a list of strings, for instance.

In Python, the same idea:

numbers = [1, 2, 3, 4, 5]
squares = list(map(lambda x: x ** 2, numbers))
# [1, 4, 9, 16, 25]

Most modern languages have this baked in somewhere. JavaScript has Array.prototype.map. Python has map. Rust has .map() on iterators. It’s everywhere because the pattern is genuinely useful.

Filter

filter takes a predicate - a function that returns a boolean - and a list, and keeps only the elements for which the predicate returns True.

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

filter even [1, 2, 3, 4, 5, 6]
-- [2, 4, 6]

filter (> 3) [1, 2, 3, 4, 5]
-- [4, 5]

The type is constrained compared to map: input and output lists must have the same element type, since you’re just deciding what to keep. You’re not transforming elements, just selecting them.

These two together get you pretty far. Want the squares of all even numbers up to 100?

map (^2) (filter even [1..100])

Or with the composition operator:

(map (^2) . filter even) [1..100]

Clean and readable, and not a loop in sight!

Fold

Here’s the interesting one. fold (or reduce in many languages) is the most general of the three, and also the one that trips people up at first. The idea: collapse a list down to a single value by repeatedly applying a combining function.

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

There are a lot of arguments here. Let’s break it down. foldr takes:

  1. A function (a -> b -> b) - it takes an element and an accumulator, and returns a new accumulator
  2. An initial value for the accumulator
  3. The list to process

An example: summing a list.

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

What happens step by step: (1 + (2 + (3 + (4 + (5 + 0))))). The 0 is the starting accumulator, and (+) combines each element with the running total. You can use any combining function and any starting value - that’s what makes fold so general.

Concatenating strings:

foldr (++) "" ["hello", " ", "world"]
-- "hello world"

Building a list in reverse:

foldr (\x acc -> acc ++ [x]) [] [1, 2, 3]
-- [3, 2, 1]

Here’s the part I love: map and filter are both just special cases of fold. You can implement them with it!

myMap :: (a -> b) -> [a] -> [b]
myMap f = foldr (\x acc -> f x : acc) []

myFilter :: (a -> Bool) -> [a] -> [a]
myFilter p = foldr (\x acc -> if p x then x : acc else acc) []

myMap builds up a new list by prepending f x for each element. myFilter does the same but only prepends when the predicate holds. This isn’t just a party trick - it reveals that fold is essentially the primitive operation for processing lists, and map and filter are conveniences built on top of it.

In Python, reduce lives in functools:

from functools import reduce

reduce(lambda acc, x: acc + x, [1, 2, 3, 4, 5], 0)
# 15

reduce(lambda acc, x: acc + [x * 2], [1, 2, 3], [])
# [2, 4, 6]  (effectively a map)

Putting Them Together

The real power comes from chaining these operations. Say you have a list of user records and want the total age of all users over 18:

data User = User { name :: String, age :: Int }

users :: [User]
users = [User "Alice" 30, User "Bob" 15, User "Carol" 25, User "Dan" 17]

totalAdultAge :: Int
totalAdultAge = foldr (+) 0 . map age . filter ((>= 18) . age) $ users
-- 55

Reading right to left: filter to adults, extract their ages, sum them up. Three functions, no loops, no intermediate variables - just a pipeline. Once you get comfortable reading this style, it’s actually quite expressive!

map, filter, and fold are not exotic abstractions. They’re workhorses. Any time you find yourself writing a loop that transforms a collection, builds up a result, or selects elements - there’s almost certainly a cleaner way to express it with one of these three. Getting them in your fingers is worth the effort.

← Back to Writing