Recursive Functions on Lists
Computing with lists
There are two approaches to working with lists:
- Write functions to do what you want, using recursive definitions that traverse the list structure.
- Write combinations of the standard list processing functions.
- The second approach is preferred, but the standard list processing functions do need to be defined, and those definitions use the first approach (recursive definitions).
- We’ll cover both methods.
Recursion on lists
- A list is built from the empty list and the function . In Haskell, the function is actually written as the operator , in other words : is pronounced as
- Every list must be either
- for some (the head of the list) and (the tail)
where is pronounced as
- The recursive definition follows the structure of the data:
- Base case of the recursion is .
- Recursion (or induction) case is .
Some examples of recursion on lists
Recursive definition of length
The length of a list can be computed recursively as follows:
length :: [a] -> Int length  = 0 # the base case length (x:xs) = 1 + length xs # recursion case
Recursive definition of filter
- filter is given a predicate (a function that gives a Boolean result) and a list, and returns a list of the elements that satisfy the predicate.
filter :: (a->Bool) -> [a] -> [a]
Filtering is useful for the “generate and test” programming paradigm.
filter (<5) [3,9,2,12,6,4] -- > [3,2,4]
The library definition for
filter is shown below. This relies on guards, which we will investigate properly next week.
filter :: (a -> Bool) -> [a] -> [a] filter pred  =  filter pred (x:xs) | pred x = x : filter pred xs | otherwise = filter pred xs
Computations over lists
- Many computatations that would be for/while loops in an imperative language are naturally expressed as list computations in a functional language.
There are some common cases:
- Perform a computation on each element of a list:
- Iterate over a list, from left to right:
- Iterate over a list, from right to left:
- It’s good practice to use these three functions when applicable
- And there are some related functions that we’ll see later
- We can express a large computation by “chaining together” a sequence of functions that perform smaller computations
- Start with an argument of type
- Apply a function to it, getting an intermediate result of type
- Then apply a function to the intermediate result, getting the final result of type
- The entire computation (first , then ) is written as .
- This is traditional mathematical notation; just remember that in , the functions are used in right to left order.
.as the function composition operator
(.) :: (b->c) -> (a->b) -> a -> c (f . g) x = f (g x)
Performing an operation on every element of a list: map
map applies a function to every element of a list
map f [x0,x1,x2] -- > [f x0, f x1, f x2]
Composition of maps
- map is one of the most commonly used tools in your functional toolkit
A common style is to define a set of simple computations using map, and to compose them.
map f (map g xs) = map (f . g) xs
This theorem is frequently used, in both directions.
Recursive definition of map
map :: (a -> b) -> [a] -> [b] map _  =  map f (x:xs) = f x : map f xs
Folding a list (reduction)
- An iteration over a list to produce a singleton value is called a fold
- There are several variations: folding from the left, folding from the right, several variations having to do with “initialisation”, and some more advanced variations.
- Folds may look tricky at first, but they are extremely powerful, and they are used a lot! And they aren’t actually very complicated.
Left fold: foldl
- foldl is fold from the left
- Think of it as an iteration across a list, going left to right.
- A typical application is
- The is an initial value
- The argument is a list of values which we combine systematically using the supplied function
- A useful intuition: think of the argument as an “accumulator”.
The function takes the current value of the accumulator and a list element, and gives the new value of the accumulator.
foldl :: (b->a->b) -> b -> [a] -> b
Examples of foldl with function notation
Examples of foldl with infix notation
In this example, + denotes an arbitrary operator for f; it isn’t supposed to mean specifically addition.
foldl (+) z  -- > z foldl (+) z [x0] -- > z + x0 foldl (+) z [x0,x1] -- > (z + x0) + x1 foldl (+) z [x0,x1,x2] -- > ((z + x0) + x1) + x2
Recursive definition of foldl
foldl :: (b -> a -> b) -> b -> [a] -> b foldl f z0 xs0 = lgo z0 xs0 where lgo z  = z lgo z (x:xs) = lgo (f z x) xs
Right fold: foldr
- Similar to , but it works from right to left
foldr :: (a -> b -> b) -> b -> [a] -> b
Examples of foldr with function notation
Examples of foldr with operator notation
foldr (+) z  -- > z foldr (+) z [x0] -- > x0 + z foldr (+) z [x0,x1] -- > x0 + (x1 + z) foldr (+) z [x0,x1,x2] -- > x0 + (x1 + (x2 + z))
Recursive definition of foldr
foldr :: (a -> b -> b) -> b -> [a] -> b foldr k z = go where go  = z go (y:ys) = y `k` go ys
Relationship between foldr and list structure
We have seen that a list
[x0,x1,x2] can also be written as
x0 : x1 : x2 : 
Folding (:) over a list using the empty list  as accumulator gives:
foldr (:)  [x0,x1,x2] -- > x0 : x1 : x2 : 
This is identical to constructing the list using (:) and  ! We can formalise this relationship as follows:
Some applications of folds
sum xs = foldr (+) 0 xs product xs = foldr (*) 1 xs
We can actually “factor out” the that appears at the right of each side of the equation, and write:
sum = foldr (+) 0 product = foldr (*) 1
(This is sometimes called “point free” style because you’re programming solely with the functions; the data isn’t mentioned directly.)
© University of Glasgow