Haskell 6: Higher-Order Functions, Lambda Expressions, and Function Composition

Part 6 of Haskell from First Principles.

Treat each snippet as an independent example; later versions replace earlier definitions with the same name. Names beginning with my are pedagogical implementations. Use the existing Prelude functions map, filter, foldr, foldl, curry, and uncurry in ordinary programs. Fold signatures below are specialized to lists; the modern Prelude generalizes folds through Foldable.

Part 4 developed list recursion, and Part 5 applied it to custom data structures and trees.

For example, we defined:

doubleAll :: Num a => [a] -> [a]
doubleAll [] = []
doubleAll (x:xs) = (2*x) : doubleAll xs

This function doubles every element in a list.

But suppose we also want to square every element, add one to every element, or convert every element into a string.

Passing a function as an argument lets one traversal support all of these transformations.

This is the central idea of higher-order functional programming.

Six closely related concepts make this possible:

1. Lambda expressions: defining anonymous functions.
2. Currying and partial application.
3. Higher-order functions: map and filter.
4. Recursive aggregation: foldr and foldl.
5. Function composition: ..
6. Function application and operator syntax: $, infix notation, and sections.

The examples connect syntax with type inference and evaluation semantics.

---

6.1 Functions are values

Recall the function:

square :: Int -> Int
square x = x * x

In Haskell, square is a value whose type is Int -> Int.

This means we can assign it another name:

f :: Int -> Int
f = square

And then:

f 5    -- 25

Notice that we did not write:

f x = square x

Both definitions are valid, but f = square is enough because square already denotes a function.

More interestingly, a function can receive another function as an argument.

Consider:

apply :: (Int -> Int) -> Int -> Int
apply f x = f x

We can evaluate:

apply square 5    -- 25

Here, square is passed as an argument to apply.

Let us examine the type:

(Int -> Int) -> Int -> Int

Because -> associates to the right, this means:

(Int -> Int) -> (Int -> Int)

The first argument is a function of type Int -> Int, and the result of applying that argument is another function Int -> Int.

The expression apply square itself is a function.

This leads to an important definition:

A higher-order function is a function that takes another function as an argument or returns a function as its result.

In Haskell, higher-order functions are completely ordinary. No special declaration is required.

6.2 Lambda expressions: anonymous functions

So far, every function we have defined has a name.

For example:

increment x = x + 1

But sometimes we only need a function temporarily, without giving it a name.

Haskell uses the syntax:

\x -> x + 1

This is called a lambda expression.

The general grammar is:

\parameter -> expression

The backslash \ introduces the function, the parameter is its input, and the expression after -> is its body.

Mathematically, it corresponds to:

$$\lambda x.x+1.$$

The use of \ comes from its visual resemblance to the Greek letter $\lambda$.

Named functions versus lambda expressions

These two definitions mean the same thing:

increment x = x + 1

and:

increment = \x -> x + 1

Both define the function:

$$f(x)=x+1.$$

The difference is that a lambda expression creates a function without requiring a separate name.

We can apply it immediately:

(\x -> x + 1) 5

which evaluates to 6.

Let us evaluate it by substitution:

$$(\lambda x.x+1)(5)=5+1=6.$$

The parentheses group the lambda expression so that the entire function is applied to 5.

Multiple parameters

A lambda can have several parameters:

\x y -> x + y

For example:

(\x y -> x + y) 3 5

evaluates to 8.

The syntax:

\x y -> x + y

is shorthand for:

\x -> \y -> x + y

This brings us directly to currying.

Lambda expressions and lexical scope

Consider:

addN :: Int -> Int -> Int
addN n = \x -> n + x

The lambda refers to n, which was introduced outside it.

For example:

addN 3 10    -- 13

The function \x -> n + x remembers the binding of n in its lexical environment. This is called a closure.

It is another reason why functions are more than merely named blocks of code: functions can be created dynamically while referring to variables in their enclosing scope.

---

6.3 Currying and partial application, revisited

In Block 2, we briefly introduced currying. Now we can understand it more precisely.

Consider:

add :: Int -> Int -> Int
add x y = x + y

This definition is equivalent to:

add = \x -> \y -> x + y

In particular, add does not fundamentally take a pair of arguments.

Instead, it takes one argument and returns a function that accepts the second argument.

Expression	Type	Interpretation
add	Int -> Int -> Int	Awaits the first argument
add 3	Int -> Int	Equivalent to \y -> 3 + y
add 3 5	Int	Produces 8

Thus:

add 3

is itself a function, equivalent in behavior to:

\y -> 3 + y

We can define:

addThree :: Int -> Int
addThree = add 3

Then:

addThree 10    -- 13

This technique is called partial application.

Currying versus tuples

There is an important grammatical distinction between:

add :: Int -> Int -> Int

and:

addPair :: (Int, Int) -> Int

The first function is curried.

The second takes a single argument that happens to be a tuple.

addPair (x,y) = x + y

They are called differently:

add 3 5         -- 8
 
addPair (3,5)   -- 8

Their types are different:

$$\mathrm{Int}\to (\mathrm{Int}\to \mathrm{Int})$$

versus

$$(\mathrm{Int},\mathrm{Int})\to \mathrm{Int}.$$

We can convert between these representations:

curry :: ((a,b) -> c) -> a -> b -> c
 
uncurry :: (a -> b -> c) -> (a,b) -> c

These are existing functions in Haskell’s standard Prelude.

For example:

curry addPair 3 5    -- 8
 
uncurry add (3,5)    -- 8

This is a useful demonstration that curried functions and functions of tuples encode closely related mathematical information, even though their types are different.

---

6.4 Higher-order functions: map

Let us return to the problem from the beginning of this block.

Previously, we defined:

doubleAll [] = []
doubleAll (x:xs) = (2*x) : doubleAll xs

Suppose we also want:

squareAll [] = []
squareAll (x:xs) = (x*x) : squareAll xs

The two functions have almost identical recursive structure.

The only difference is what happens to each element.

We can capture this pattern in a more general function.

Defining map from first principles

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

Let us derive its type.

The input list has type [a].

We want the output list to have type [b].

Therefore, the function applied to each element must have type:

a -> b

Thus the complete type is:

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

Haskell already provides this function under the name map.

Examples

map (\x -> x * 2) [1,2,3]
-- [2,4,6]

map (\x -> x * x) [1,2,3]
-- [1,4,9]

map (\x -> x + 1) [1,2,3]
-- [2,3,4]

Or using named functions:

square x = x * x

After loading the definition:

ghci> map square [1,2,3,4]
[1,4,9,16]

How map evaluates

Consider:

map square [1,2,3]

The recursive definition gives:

$$\begin{array}{rl}\mathrm{map}(f,[1,2,3])& =f(1):\mathrm{map}(f,[2,3])\\ & =f(1):f(2):\mathrm{map}(f,[3])\\ & =f(1):f(2):f(3):[].\end{array}$$

When $f(x)=x^2$, the result is:

$$[1,4,9].$$

The important insight is that map abstracts away the mechanics of list traversal.

The programmer only specifies the transformation.

map can change element types

For example:

map show [1,2,3]

returns:

["1","2","3"]

Here:

show :: Show a => a -> String

So map show transforms a list of values into a list of strings.

This is why map has two different type variables:

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

The input and output element types need not be the same.

---

6.5 filter: selecting elements using a predicate

Another common operation is selecting elements that satisfy a condition.

For example, we might want all positive integers from a list.

Previously, we could write:

positives [] = []
 
positives (x:xs)
  | x > 0     = x : positives xs
  | otherwise = positives xs

But again, the recursive structure is general.

Let us define:

myFilter :: (a -> Bool) -> [a] -> [a]
 
myFilter p [] = []
 
myFilter p (x:xs)
  | p x       = x : myFilter p xs
  | otherwise = myFilter p xs

The function p is called a predicate: it takes a value and returns a Boolean.

Haskell provides this function as filter.

Examples:

filter (\x -> x > 0) [-3,2,0,5,-1]
-- [2,5]

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

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

Why is the type different from map?

Compare:

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

with:

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

map transforms each element, possibly changing its type.

filter retains or removes existing elements. Therefore, its output element type is the same as its input element type.

This difference follows directly from the operations’ semantics.

---

6.6 foldr: the general pattern behind list recursion

A fold captures a more general recursion pattern.

Recall three recursive functions from Block 4.

Sum of a list

sumList [] = 0
sumList (x:xs) = x + sumList xs

Product of a list

productList [] = 1
productList (x:xs) = x * productList xs

Length of a list

lengthList [] = 0
lengthList (_:xs) = 1 + lengthList xs

Notice their common structure:

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

Here, z is the base-case result and g combines the current element with the recursively computed result.

We can abstract over both z and g.

Deriving foldr

myFoldr :: (a -> b -> b) -> b -> [a] -> b
 
myFoldr g z [] = z
 
myFoldr g z (x:xs) =
  g x (myFoldr g z xs)

This is the definition of the standard function foldr, which stands for fold right.

Its type is:

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

Let us unpack this type carefully.

The combining function has type:

a -> b -> b

It takes an element of type a and an accumulated result of type b, and produces a new result of type b.

The second argument, z, supplies the base-case value of type b.

The third argument is a list of type [a].

Finally, the result has type b.

How foldr expands

Consider:

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

By the recursive definition:

$$\begin{array}{rl}& \mathrm{foldr}(+,0,[1,2,3])\\ & =1+\mathrm{foldr}(+,0,[2,3])\\ & =1+(2+\mathrm{foldr}(+,0,[3]))\\ & =1+(2+(3+\mathrm{foldr}(+,0,[])))\\ & =1+(2+(3+0))\\ & =6.\end{array}$$

More generally:

$$\boxed{\mathrm{foldr}(f,z,[x_1,x_2,x_3])=f(x_1,f(x_2,f(x_3,z)))}$$

foldr f z [1,2,3]
= f 1 (f 2 (f 3 z))

This is a right-nested expression, not a promise to evaluate the rightmost part first. The combining function determines how much of its recursive argument is demanded.

Expressing familiar functions using foldr

Sum:

sumList :: Num a => [a] -> a
sumList = foldr (+) 0

Product:

productList :: Num a => [a] -> a
productList = foldr (*) 1

Length:

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

For length, the combining function ignores the element itself and increments the count.

Even map can be expressed using foldr

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

Let us inspect this:

• The base value is the empty list [].
• For each element x, apply f x.
• Prepend that result to the accumulated list acc.

Similarly:

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

This is a significant result.

Many ordinary recursive list functions are special cases of foldr.

In fact, foldr captures the general pattern of replacing the empty-list constructor [] with a base value, and each cons constructor (:) with a combining function.

In Block 4, we saw that every finite list has the structure:

$$x_1:x_2:\cdots :x_n:[].$$

foldr replaces:

$$(:)⟼f,[]⟼z.$$

This structural interpretation is more fundamental than simply thinking of foldr as an accumulator loop.

---

6.7 foldl: folding from the left

Haskell also provides:

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

Its definition is:

myFoldl :: (b -> a -> b) -> b -> [a] -> b
 
myFoldl f acc [] = acc
 
myFoldl f acc (x:xs) =
  myFoldl f (f acc x) xs

Compare:

foldr f z [1,2,3]

which has the structure:

$$f(1,f(2,f(3,z))).$$

And:

foldl f z [1,2,3]

which has the structure:

$$f(f(f(z,1),2),3).$$

For finite, fully defined lists, an associative operation with its identity as the base makes the two folds agree. Exact Integer addition with base 0 is one example. Floating-point addition is not associative in general.

But for non-associative operations, they can differ.

For example:

foldr (-) 0 [1,2,3]    -- 2

because:

$$1-(2-(3-0))=2.$$

But:

foldl (-) 0 [1,2,3]    -- -6

because:

$$((0-1)-2)-3=-6.$$

Comparison of the two folds

Property	foldr	foldl
Combining function	a -> b -> b	b -> a -> b
Nesting	Right-associated	Left-associated
Base value	At the right end	At the left end
Can produce useful results on some infinite lists?	Yes, depending on f	No: it must reach the end of the list spine
Typical use	Recursive structures, lazy list transformations	Left-to-right accumulation

A note about performance

Because Haskell is lazy, foldl can accumulate unevaluated expressions, sometimes causing excessive memory use.

For strict numerical accumulation, a common alternative is foldl' from Data.List. Put the import at the top of a module, before its definitions:

import Data.List (foldl')
 
sumStrict :: [Int] -> Int
sumStrict = foldl' (+) 0

foldl' forces the accumulator at each step to weak head normal form, avoiding the usual buildup of lazy accumulator expressions.

Weak head normal form exposes the outer constructor; it does not recursively evaluate fields of a tuple, list, or record. A structured accumulator may therefore need additional care. See the standard foldl' documentation.

For now, the key goal is to understand the difference between the two folding structures.

---

6.8 Function composition: .

We often want to combine functions.

Suppose:

double x = x * 2
 
increment x = x + 1

We want a function that first increments its input, then doubles the result.

We could write:

f x = double (increment x)

Haskell provides a function-composition operator:

(.)

So we can write:

f = double . increment

The mathematical meaning is:

$$(f\circ g)(x)=f(g(x)).$$

In Haskell:

(f . g) x = f (g x)

Thus:

(double . increment) 3

evaluates to:

$$\mathrm{double}(\mathrm{increment}(3))=\mathrm{double}(4)=8.$$

The type of composition

Haskell defines:

(.) :: (b -> c) -> (a -> b) -> a -> c

This is worth deriving.

Suppose:

$$g:A\to B$$

and

$$f:B\to C.$$

Then their composition is:

$$f\circ g:A\to C.$$

So the Haskell type follows:

(b -> c) -> (a -> b) -> a -> c

The middle type b must match: it is the output type of g and the input type of f.

A --g--> B --f--> C
\______________/
      f . g

Composition with map and filter

Suppose we want to compute the sum of the squares of all positive elements in a list.

We can write:

sumPositiveSquares :: [Int] -> Int
 
sumPositiveSquares xs =
  sum (map (\x -> x*x) (filter (>0) xs))

This is correct but has many nested parentheses.

Using function composition:

sumPositiveSquares :: [Int] -> Int
 
sumPositiveSquares =
  sum . map (\x -> x*x) . filter (>0)

Let us interpret the composition from right to left:

Stage	Value
Input	[-2,1,3,-4,5]
filter (>0)	[1,3,5]
map (\x -> x*x)	[1,9,25]
sum	35

Notice that this code describes a transformation pipeline.

There are no explicit loops or mutable variables.

Composition is associative

For appropriately typed functions:

$$(f\circ g)\circ h=f\circ (g\circ h).$$

Correspondingly:

(f . g) . h

and:

f . (g . h)

represent the same composed function.

This algebraic property is useful when constructing larger computations from smaller pieces.

---

6.9 The $ operator: function application with low precedence

Another common Haskell operator is:

($)

Its type is:

($) :: (a -> b) -> a -> b

And its basic behavior is:

f $ x = f x

So why do we need it?

Because $ has very low precedence.

Consider:

sum (map square [1,2,3])

We can write:

sum $ map square [1,2,3]

The meaning is identical.

The $ operator allows everything to its right to be treated as the argument expression.

Compare:

f (g (h x))

with:

f $ g $ h x

Both mean the same thing.

$ versus .

These operators are related but different.

Operator	Meaning	Example
.	Compose functions	f . g
$	Apply a function to an argument	f $ x

For example:

square . increment

produces a new function.

But:

square $ increment 5

produces a value.

The second expression is equivalent to:

square (increment 5)

This distinction is important:

Composition builds a function; application evaluates a function at an argument when its result is demanded.

---

6.10 Infix operators are also functions

Haskell’s syntax has another elegant feature.

Ordinary operators such as + and * are themselves functions.

For example:

3 + 5

can also be written:

(+) 3 5

Both evaluate to 8.

Why the parentheses?

Because + normally appears in infix position, between two arguments.

Putting it in parentheses allows us to use it as an ordinary prefix function.

Its type is:

(+) :: Num a => a -> a -> a

This is simply a curried function.

Partial application of operators

Therefore, we can write:

addThree = (+) 3

And evaluate:

addThree 5    -- 8

Haskell also provides a shorter syntax called an operator section.

For example:

(+3)

means:

\x -> x + 3

Similarly:

(*2)

means:

\x -> x * 2

And:

(>0)

means:

\x -> x > 0

These forms are convenient with higher-order functions:

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

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

Left and right sections are different

For an operator such as subtraction, argument order matters.

For example:

(10-)

means:

\x -> 10 - x

So:

map (10-) [1,2,3]
-- [9,8,7]

By contrast, (-1) in Haskell is interpreted as a negative numeric literal, not as a function subtracting 1.

To create that function, use:

subtract 1

or:

\x -> x - 1

This is one of the small grammatical details worth remembering.

Named functions can also be used as infix operators

For example:

div 10 3

and:

10 `div` 3

both evaluate to 3.

Backticks allow an ordinary function name to appear in infix position.

This is why we have previously written:

10 `div` 3

instead of:

div 10 3

Both are valid.

---

6.11 Reading complex function types

Now that we understand higher-order functions, let’s practice interpreting their types.

Consider:

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

The first argument is a function from a to b.

The second argument is a list of a.

The result is a list of b.

Now consider:

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

The predicate takes an a and returns Bool.

The result is a list of the original element type.

Finally:

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

The combining function takes one list element and one recursive result, and returns a new recursive result.

A useful technique is to parse types from right to left.

For example:

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

The final result type is [b].

Immediately to its left is an argument of type [a].

To the left of that is an argument of type (a -> b).

This is a consequence of right-associativity of ->.

A slightly more interesting example

Consider:

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

This works with many different types:

applyTwice (+1) 3
-- 5

applyTwice not True
-- True

We can use it to apply a list transformation twice:

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

Why?

Because:

map (+1)

has a type of the form:

Num a => [a] -> [a]

So it can be supplied to applyTwice, with the type variable of applyTwice instantiated to a list type.

This illustrates how Haskell can compose abstractions at different levels without introducing any new syntax.

---

6.12 Laziness and higher-order functions

Lazy evaluation has an immediate consequence for higher-order functions: they can sometimes consume and produce only a finite prefix of an infinite structure.

Consider:

map (+1) [1..]

The list [1..] is infinite.

Yet Haskell can process it because map produces its output incrementally.

For example:

take 5 (map (+1) [1..])

evaluates to:

[2,3,4,5,6]

The entire infinite list does not need to be constructed.

Similarly, foldr can sometimes work with infinite lists.

For example:

foldr (\x _ -> x) 0 [1..]

evaluates to 1.

The combining function returns the first element and ignores the recursive result, so the tail does not need to be evaluated.

But:

foldr (+) 0 [1..]

does not produce a finite result, because addition requires the accumulated sum of the entire infinite list.

This is why the difference between a function’s mathematical structure and its evaluation behavior is important in Haskell.

---

6.13 The grammar learned in Block 6

We can now extend our simplified expression grammar.

Expression :=
    ...
  | \Pattern -> Expression
  | \Pattern Pattern ... -> Expression
  | Expression Expression
  | Expression Operator Expression
  | (Operator)
  | (Operator Expression)
  | (Expression Operator)

Examples:

\x -> x + 1
 
\x y -> x + y
 
(\x -> x * x) 5
 
map (+1) [1,2,3]
 
filter (>0) [-1,2,3]
 
sum . map square
 
sum $ map square [1,2,3]

Three grammatical rules are especially important.

Rule	Example	Interpretation
Application associates left	f x y	(f x) y
Function arrows associate right	a -> b -> c	a -> (b -> c)
Lambda body extends rightward	\x -> x + 1	The body is the entire expression to its right, unless grouping restricts it

For instance:

(\x -> x + 1) 3

works because the parentheses isolate the lambda expression before it is applied.

Also remember that function application has higher precedence than ordinary infix operators:

square 3 + 4

means:

(square 3) + 4

not:

square (3 + 4)

---

6.14 Exercises

These exercises range from syntax and type inference to program construction.

Try each exercise before opening its solution. The undefined expressions in skeletons mark code to replace; evaluating an unfinished skeleton raises an error.

Exercise 6.1

Evaluate this lambda application.

(\x -> x * x + 1) 4

Solution

17

Substitution gives 4 * 4 + 1 = 17.

Exercise 6.2

Infer the most general type.

f g x = g (g x)

Solution

f :: (a -> a) -> a -> a

The output of g is passed back into the same function, so its input and output types must agree.

Exercise 6.3

Find the resulting list.

map (\x -> x + 1) (filter even [1,2,3,4,5])

Solution

[3,5]

filter selects [2,4], then map adds 1 to each value.

Exercise 6.4

Rewrite the recursion using foldr.

countTrue [] = 0
countTrue (x:xs)
  | x         = 1 + countTrue xs
  | otherwise = countTrue xs

Solution

countTrue :: [Bool] -> Int
countTrue = foldr (\x n -> if x then 1+n else n) 0

The base value is 0. The combining function increments the count exactly when the current element is True.

Exercise 6.5

Use composition to retain positive elements, double them, and sum the results.

f :: [Int] -> Int
f = undefined

Solution

f = sum . map (*2) . filter (>0)

The composition applies filter, then map, then sum.

Exercise 6.6

Predict both fold results.

foldr (-) 0 [1,2,3]
foldl (-) 0 [1,2,3]

Solution

foldr (-) 0 [1,2,3] -- 2
foldl (-) 0 [1,2,3] -- -6

The right fold builds 1-(2-(3-0)); the left fold builds ((0-1)-2)-3.

---

6.15 A deeper perspective: computation as composition

Higher-order functions let a program describe a computation in terms of reusable parts.

Consider the function:

sumPositiveSquares =
  sum . map (\x -> x*x) . filter (>0)

This definition contains no explicit recursion, even though it processes an arbitrarily long list.

Where did the recursion go?

It has been encapsulated inside reusable abstractions:

• filter handles traversal and selection.
• map handles traversal and transformation.
• sum handles aggregation.

The programmer describes how transformations are composed rather than implementing the traversal repeatedly.

This suggests a general principle:

Separate the structure of computation from the specific operations performed during that computation.

For lists, map, filter, and foldr encapsulate common computation patterns.

For trees, we can construct similar functions, as we saw in Block 5:

mapTree :: (a -> b) -> Tree a -> Tree b

The similarity between map and mapTree is not accidental.

Both preserve a data structure while transforming its contained values.

This shared shape-preserving behavior is the subject of Functor in Part 8.

There is also a mathematical connection between foldr and recursive data types. Recall:

$$\mathrm{List}(A)=1+A\times \mathrm{List}(A).$$

A fold replaces this recursive construction with an algebra for combining results:

$$g:A\times B\to B,z\in B.$$

The same idea generalizes to trees and other recursive types. The general pattern is called a catamorphism. The list equations already give a concrete way to understand and use it.

---

6.16 Summary

Concept	Syntax	Meaning
Lambda	\x -> x + 1	Anonymous function
Currying	a -> b -> c	Function returning a function
Partial application	add 3	Supply some arguments
Higher-order function	applyTwice f x	Function accepting another function
Map	map f xs	Transform every element
Filter	filter p xs	Select elements
Fold right	foldr f z xs	Right-nested structural reduction
Fold left	foldl f z xs	Left-nested accumulation
Composition	f . g	Construct a composed function
Application operator	f $ x	Apply with low precedence
Operator section	(+1)	Partially apply an infix operator

The three most important functions to understand thoroughly are:

map    :: (a -> b) -> [a] -> [b]
 
filter :: (a -> Bool) -> [a] -> [a]
 
foldr  :: (a -> b -> b) -> b -> [a] -> b

Together, they express a large fraction of common list-processing algorithms.

A particularly valuable exercise is to implement map and filter using foldr, and then derive the type signatures without looking them up.

---

← Part 5 · Series index · Part 7 →

Adapted from Block 6 of the GPT-produced Haskell tutorial, with editorial and technical corrections.