0096: Email Tutorials – Higher‐Order Functions in Haskell

FP10 Graham Hutton Video

Table of Contents

1. What “higher-order” means
2. A first example: twice
3. Why higher-order functions are useful
4. map: apply a function to every element
5. filter: keep only elements that satisfy a predicate
6. The big one: foldr (fold-right)
7. Thinking about foldr as “replace (:) and []”
8. More power than you expect: length, reverse, and (++) via foldr
9. Why foldr matters in real Haskell (reasoning + compiler optimizations)
10. Other handy higher-order library functions: (.), all, any, takeWhile, dropWhile
11. Exercises from the lecture (with solutions)
12. Glossary

1. What “higher-order” means

A function is called higher-order if it does at least one of these:

1. Takes a function as an argument, or
2. Returns a function as a result. ([youtube.com][1])

This sounds fancy, but it’s extremely practical: higher-order functions let you package common programming patterns (“idioms”) into reusable building blocks.

2. A first example: twice

Here’s a simple higher-order function from the lecture:

twice :: (a -> a) -> a -> a
twice f x = f (f x)

What it does:

• twice takes a function f
• then takes a value x
• applies f to x two times

Example usage:

twice (+1) 3
-- (+1) ((+1) 3) = (+1) 4 = 5

Why must f have type (a -> a) (not (a -> b))?

Because after the first call f x, you get some result, and you must be able to feed that result into f again. That only works if the output type is the same as the input type.

3. Why higher-order functions are useful

Higher-order functions are useful for three big reasons:

1. Capture patterns once, reuse everywhere. If you notice you keep doing the same “shape” of work (like “apply something twice”, “transform each element”, “keep only the good ones”), you can turn that pattern into a function, and pass the changing part (the function) as an argument. ([youtube.com][1])

2. Build domain-specific languages (DSLs). Many Haskell libraries are basically collections of higher-order functions that feel like a mini-language for a domain (parsing, pretty-printing, GUIs, etc.). ([youtube.com][1])

3. Enable algebraic reasoning + optimizations. Higher-order functions like foldr have “laws” (e.g., fusion-style ideas) that can help reason about and optimize programs. The lecture mentions this as motivation for why foldr shows up so much. ([youtube.com][1])

4. map: apply a function to every element

4.1 What it does

map takes a function and a list, and applies the function to each element:

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

Example:

map (+1) [1,3,5,7]
-- [2,4,6,8]

4.2 How you can define it (list comprehension)

map f xs = [f x | x <- xs]

This reads as: “build the list of f x for each x drawn from xs.”

4.3 How you can define it (recursion)

map f []     = []
map f (x:xs) = f x : map f xs

Why show the recursive version if the comprehension version is so short? Because recursive definitions are easier to prove properties about using induction (the lecture notes this, even if you won’t do proofs yet). ([youtube.com][1])

5. filter: keep only elements that satisfy a predicate

5.1 What it does

A predicate is just a function that returns True or False.

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

Example:

filter even [1..10]
-- [2,4,6,8,10]

5.2 Definition using a list comprehension

filter p xs = [x | x <- xs, p x]

This reads as: “take x from xs, and keep it only if p x is true.”

5.3 Definition using recursion

filter p [] = []
filter p (x:xs)
  | p x       = x : filter p xs
  | otherwise =     filter p xs

The idea is simple: check the head; keep it or drop it; then recurse on the tail.

6. The big one: foldr (fold-right)

The lecture’s key observation is that many list functions follow this pattern:

• Base case for [] returns a constant value v
• Recursive case combines the head x with the processed tail using an operator/function

foldr packages that pattern so you don’t have to write the recursion every time. ([youtube.com][1])

6.1 Type and definition

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f v []     = v
foldr f v (x:xs) = f x (foldr f v xs)

Read it like this:

• If the list is empty, return v.
• Otherwise, apply f to the head x and the folded tail.

6.2 One-line definitions of common functions

sum     = foldr (+) 0
product = foldr (*) 1
and     = foldr (&&) True
or      = foldr (||) False

These work because each matches the same recursive “shape.”

7. Thinking about foldr as “replace (:) and []”

A very beginner-friendly mental model from the lecture is:

foldr f v replaces every (:) with f, and replaces the final [] with v. ([youtube.com][1])

Example with sum:

List structure:

[1,2,3]  ==  1 : (2 : (3 : []))

Fold:

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

Same idea for product:

foldr (*) 1 [1,2,3]
== 1 * (2 * (3 * 1))
== 6

This “replacement” viewpoint makes foldr feel much less mysterious.

8. More power than you expect: length, reverse, and (++) via foldr

A surprise from the lecture: even functions that don’t look like the pattern can still be written with foldr, because the combining function can ignore or rearrange arguments.

8.1 length using foldr

Recursive length adds 1 for each element, ignoring the element itself. So we pass a function that ignores its first argument:

length :: [a] -> Int
length = foldr (\_ n -> 1 + n) 0

• \_ n -> 1 + n means: ignore the element, add 1 to the running count.

8.2 reverse using foldr

Recursive reverse idea: reverse the tail, then append the head at the end. With foldr, we can do:

reverse :: [a] -> [a]
reverse = foldr (\x xs -> xs ++ [x]) []

This is not necessarily the fastest way, but it demonstrates expressiveness: the folding function can “flip” the order by appending at the end.

8.3 (++) using foldr

This one is beautifully intuitive with the “replace constructors” idea:

(++) :: [a] -> [a] -> [a]
xs ++ ys = foldr (:) ys xs

Interpretation:

• Copy the first list by keeping its (:)
• When you reach its [], replace it with ys

9. Why foldr matters in real Haskell

The lecture gives three motivations:

1. Some definitions become very short and clear (like sum, product, and, or). ([youtube.com][1])
2. You can reason about fold-based code using fold “laws” (fusion, etc.). ([youtube.com][1])
3. Compilers use fold-based structure to optimize code (the lecture mentions this as a practical reason it appears in libraries). ([youtube.com][1])

So even if you don’t do formal proofs, fold-based style can still help you write code the compiler can optimize well.

10. Other handy higher-order library functions

10.1 Function composition (.)

Composition means “do g first, then do f”:

(.) :: (b -> c) -> (a -> b) -> (a -> c)
f . g = \x -> f (g x)

Example from the lecture idea: odd means “not even”:

odd = not . even

This is higher-order because it both takes functions and returns a function.

10.2 all and any

• all p xs is True if every element satisfies p
• any p xs is True if at least one element satisfies p

They’re often defined using mapping predicates over a list and combining results. ([youtube.com][1])

10.3 takeWhile and dropWhile

• takeWhile p xs keeps taking from the front while p stays true; stops at first failure.
• dropWhile p xs drops from the front while p stays true; returns the rest.

These are extremely useful for simple parsing tasks (splitting at a space, skipping leading spaces, etc.). ([youtube.com][1])

11. Exercises from the lecture (with answers)

Exercise 1: “Higher-order functions that return functions are better known as…?”

Answer: Curried functions. ([youtube.com][1])

Why? Because a curried type like:

take :: Int -> [a] -> [a]

really means:

take :: Int -> ([a] -> [a])

So after supplying the first argument (Int), you get back a function that waits for the list.

Exercise 2: Rewrite this list comprehension using map and filter

Given:

[f x | x <- xs, p x]

Correct rewrite:

map f (filter p xs)

Why this order? The comprehension first filters by p x, then applies f to what remains. The blog-style Chapter 7 exercise solution page shows exactly this form. ([Connor Baker][5])

Common mistake (wrong order):

filter p (map f xs)   -- not equivalent in general

12. Glossary

Higher-order function: A function that takes a function as input or returns a function as output. ([youtube.com][1])

Predicate: A function that returns Bool (a property/test), e.g. even :: Int -> Bool.

Curried function: A multi-argument function written as a chain of single-argument functions, e.g. a -> b -> c means a -> (b -> c).

Lambda expression: An anonymous function, e.g. \x -> x + 1.

Map: Applies a function to every element of a list, producing a new list.

Filter: Keeps only the elements of a list that satisfy a predicate.

Fold (foldr): A general pattern for consuming a list by combining elements with a function and a base value.

foldr: “Fold right”; processes a list from the right side conceptually: f x (foldr f v xs).

Function composition (.): Combines two functions into one pipeline: (f . g) x = f (g x).

takeWhile / dropWhile: List-processing functions that stop when a predicate first fails (takeWhile keeps the prefix; dropWhile removes the prefix).

Buy Book

Quizz & Progress Badge NFT