Unit 5: Higherorder functions
The functions map
and filter
The higherorder function map
takes a function f
and a list xs
as its arguments and it applies f
to each element of xs
:
map f [x_{1}, x_{2}, ..., x_{n}] = [f x_{1}, f x_{2}, ..., f x_{n}]
It can be defined as follows:
map :: (a > b) > [a] > [b]
map f [] = []
map f (x:xs) = f x : map f xs
Let square x = x * x
.
Then we have the following:
map square [1 .. 7] = [1, 4, 9, 16, 25, 36, 49]
The higherorder function filter
takes a Booleanvalued expression
pred
and a list xs
as its arguments and it produces a sublist
of xs
as its value such that each
element in the value satisfies the
Booleanvalued expression pred
.
For example:
filter even [1 .. 10] = [2, 4, 6, 8, 10]
The higherorder function filter
can be defined like this:
filter :: (a > Bool) > [a] > [a]
filter _ [] = []
filter pred (x:xs)
 pred x = x:ys
 otherwise = ys where ys = filter pred xs
Function composition
Composition is a binary operator represented by an infix full stop:
(f.g) x
is equivalent to f (g x)
.
The type of the section (.)
is
(a > b) > (c > a) > c > b
.
Function composition is useful for many reasons.
One of them is that
f (g ( h (i (j (k x)))))
, say, can be written as
(f . g . h . i . j . k ) x
;
noting that function composition is associative.
This usefulness can be illustrated by means of the following problem:
Find the sum of the cubes of all the numbers divisible by 7 in a list
xs
of integers.
The solution is as follows:
answer :: [Int] > Int
answer xs = sum (map cube (filter by7 xs))
cube :: Int > Int
cube x = x * x * x
by7 :: Int > Bool
by7 x = x `mod` 7 == 0
But using function composition this can be written more clearly as follows:
answer :: [Int] > Int
answer = sum . map cube . filter by7
This version of answer
illustrates functionlevel definition.
When a parameter appears on the extreme left of both sides of the definition symbol =
,
both of its occurrences can be deleted.
The version in which the parameter occurs is know as an objectlevel definition.
For example, the following two definitions are equivalent;
the first is the objectlevel definition and the second the functionlevel definition:
fun xs = (filter odd . map square) xs
fun = filter odd . map square
Functionlevel definitions are also know as pointfree ones and even sometimes as pointless ones; objectlevel definitions are also known as pointlevel or pointwise ones.
The fusion law for map
Fusion laws in Haskell combine two or more computations into a single computation.
The fusion law for map
states that:
map f . map g = map (f.g)
Applying the lefthand side of this law to a list results in two traversals of its argument, whereas applying the righthand version only traverses the list once.
Combining two uses of filter
is a bit more complicated.
It requires us to define a function andPred
:
andPred :: (a > Bool) > (a > Bool) > a > Bool
andPred p q x = (p x) && (q x)
Using andPred
we have the following law in
both pointlevel and pointfree versions:
filter p (filter q xs) = filter (andPred p q ) xs
filter p . filter q = filter (andPred p q )
Function application $
Function application in Haskell is simply represented by writing a function
f
before its argument x
,
thus f x
.
However, there is also an explicit function application operator represented by the dollar sign:
($) :: (a > b) > a > b
Thus, f $ x
is the same as f x
.
Such an operator may seem unnecessary, but its use can reduce the number of parentheses
used in writing complicated expressions.
This is because it has the lowest precedence of any operator and is right associative
whereas normal function application has the highest precedence of any Haskell
operator and is left associative.
The function answer
defined above
can be written as follows:
answer xs = sum $ map cube $ filter by7 xs
Note that you cannot remove the occurrences of xs
in the above definition since filter by7 xs
is the argument of the function map cube
.
List comprehensions and map
and
filter
Every list that can be defined using a list comprehension can also be defined
using map
and filter
and visa versa.
First, I define map
and filter
using list comprehensions:
map f xs = [ f x  x < xs ]
filter pred xs = [ x  x < xs, pred x ]
Next, I show the idea behind defining arbitrary list comprehensions
using map
and filter
:
[ f x  x < xs, pred x ]
is equivalent to
map f (filter pred xs)
, which can also be written as
(map f . filter pred) xs
, using function composition.
The higherorder function iterate
Newton's method for finding positive square roots
Let x
be the positive number whose square root you are
trying to find. Then if y > 0
is a guess,
then (y + x/y)/2
is a better guess.
For example, say we want to find the positive square root of 27.3.
Let us guess 1.
Applying Newton's method, a better guess is 14.15.
Applying Newton's method again, a still better guess is 8.03966.
Applying Newton's method again, a still better guess is 5.71766.
Applying Newton's method again, a still better guess is 5.24617.
And so on.
Newton's method can be programmed straightforwardly in Haskell as follows:
root :: Float > Float
root x = rootiter x 1
rootiter :: Float > Float > Float
rootiter x y
 satisfactory x y = y
 otherwise = rootiter x (improve x y)
satisfactory :: Float > Float > Bool
satisfactory x y = abs (y*y  x) < 0.01
improve :: Float > Float > Float
improve x y = (y + x/y)/2
This, however, is quite an "imperative" solution.
A more "functional" solution uses the predefined Haskell function
iterate
:
iterate :: (a > a) > a > [a]
iterate f x = x : iterate f (f x)
The function iterate
generates an infinite list in the following way:
iterate f x = [x, f x, f (f x), f (f (f x)), f (f (f (f x))), ...]
Using iterate
it is possible to produce a more "functional" implementation of Newton's
method of finding positive square roots:
root :: Float > Float
root x = head (filter (satisfactory x) (iterate (improve x) 1))
satisfactory :: Float > Float > Bool
satisfactory x y = abs (y*y  x) < 0.01
improve :: Float > Float > Float
improve x y = (y + x/y)/2
The sieve of Eratosthenes for generating primes
 Make a list of all the positive integers starting at 2.

The first number on the list is prime; call it
p
. 
Construct a new list in which all multiples of
p
have been removed. 
Repeat the above from step (2).
The above procedure can be thought of as generating an infinite list of infinite lists. The prime numbers are the first elements of lists of integers:
[ [ 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ... ],
[ 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, ... ],
[ 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, ... ],
[ 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, ... ],
[11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, ... ], ... ]
In Haskell the sieve can be programmed like this:
primes = map head (iterate sieve [2..])
sieve (p:xs) = [ x  x < xs, x `mod` p /= 0 ]
Step (1) is represented by [2..]
.
Step (2) is represented by map head
.
Step (3) is represented by sieve
and
step (4) is represented by iterate
.
© Antoni Diller (20 September 2021)