Thinking Functionally with Haskell (12 page)

Haskell provides useful notation for enumerating lists of integers. When
m
and
n
are integers we can write

The first two notations crop up frequently in practice, the second two less so. As examples,
ghci> [0,2..11]

[0,2,4,6,8,10]

ghci> [1,3..]

[1,3,5,7,9,11 {Interrupted}

In the first example the enumeration stops at 10 because 11 isn’t even. In the second example we quickly interrupted the evaluation of an infinite list.

As a matter of fact, enumerations are not restricted to integers, but to members of yet another type class
Enum
. We won’t elaborate more on this class, except to say that
Char
is also a member:
ghci> ['a'..'z']

"abcdefghijklmnopqrstuvwxyz"

Haskell provides another useful and very attractive piece of notation, called
list comprehensions
, for constructing lists out of other lists. We illustrate with a few examples:
ghci> [x*x | x <- [1..5]]

[1,4,9,16,25]

ghci> [x*x | x <- [1..5], isPrime x]

[4,9,25]

ghci> [(i,j) | i <- [1..5], even i, j <- [i..5]]

[(2,2),(2,3),(2,4),(2,5),(4,4),(4,5)]

ghci> [x | xs <- [[(3,4)],[(5,4),(3,2)]], (3,x) <- xs]

[4,2]

Here is another example. Suppose we wanted to generate all Pythagorean triads in a given range. These are triples of numbers (
x
,
y
,
z
) such that
x
²
+
y
²
=
z
²
and 1 ≤
x
,
y
,
z
≤
n
for some given
n
. We can define

triads :: Int -> [(Int,Int,Int)]

triads n = [(x,y,z) | x <- [1..n], y <- [1..n], z <- [1..n], x*x+y*y==z*z]

Hence

ghci> triads 15

[(3,4,5),(4,3,5),(5,12,13),(6,8,10), (8,6,10),(9,12,15),(12,5,13),(12,9,15)]

That’s probably not what we want: each essentially distinct triad is generated in two different ways. Moreover, the list contains redundant triads consisting of multiples of basic triads. To improve the definition of
triad
we can restrict
x
and
y
so that
x
<
y
and
x
and
y
are coprime, meaning they have no divisors in common. As mathematicians we know that 2
x
²
cannot be the square of an integer, so the first restriction is valid. The divisors of a number can be computed by
divisors x = [d | d <- [2..x-1], x `mod` d == 0]

Hence

coprime x y = disjoint (divisors x) (divisors y)

We will leave the definition of
disjoint
as an exercise.

That means we can define

triads n = [(x,y,z) | x <- [1..n], y <- [x+1..n],

coprime x y,

z <- [y+1..n], x*x+y*y==z*z]

This definition is better than before, but let us try to make it a little faster, mainly to illustrate an important point. Since 2
x
²
<
x
²
+
y
²
=
z
²
≤
n
²
we see that
So
That suggests we can write
triads n = [(x,y,z) | x <- [1..m], y <- [x+1..n],

coprime x y,

z <- [y+1..n], x*x+y*y==z*z]

where m = floor (n / sqrt 2)

But the expression for
m
is incorrect:
n
is an
Int
and we cannot divide integers. We need an explicit conversion function, and the one to use is
fromIntegral
(not
fromInteger
because
n
is an
Int
not an
Integer
). We need to replace the definition of
m
by
m = floor (fromIntegral n / sqrt 2)
. Once again we have to be careful about what kinds of number we are dealing with and aware of the available conversion functions between them.

List comprehensions can be used to define some common functions on lists. For example,

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

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

concat xss
= [x | xs <- xss, x <- xs]

Actually, in Haskell it is the other way around: list comprehensions are translated into equivalent definitions in terms of
map
, and
concat
. The translation rules are:

[e |True]
= [e]

[e | q]
= [e | q, True]

[e | b, Q]
= if b then [e | Q] else []

[e | p <- xs, Q] = let ok p = [e | Q]

ok _ = []

in concat (map ok xs)

The definition of
ok
in the fourth rule uses a
don’t care
pattern, also called a
wild card
. The
p
in the fourth rule is a pattern, and the definition of
ok
says that the empty list is returned on any argument that doesn’t match the pattern
p
.

Another useful rule is

[e | Q1, Q2] = concat [[e | Q2] | Q1]

We can define functions over lists by pattern matching. For example,

The patterns
[]
and
x:xs
are disjoint and exhaustive, so we can write the two equations for
null
in either order. The function
null
is strict because Haskell has to know which equation to apply and that requires evaluation of the argument, at least to the extent of discovering whether it is the empty list or not. (A question: why not simply define
null = (==[])
?) We could also have written

null [] = True

null _
= False

This definition uses a don’t care pattern.

Here are two other definitions using pattern matching:

There is no equation for the pattern
[]
, so Haskell reports an error if we try to evaluate
head []
or
tail []
.

We can use
[x]
as shorthand for
x:[]
in a pattern:

last :: [a] -> a

last [x]
= x

last (x:y:ys) = last (y:ys)

The first equation has a pattern that matches a singleton list; the second has a pattern that matches a list that contains at least two elements. The standard prelude definition of
last
is slightly different:

last [x]
= x

last (_:xs) = last xs

This definition uses a don’t care pattern. The two equations have to be written in this order because
x:[]
matches both patterns.

Here is the definition of
(++)
, the concatenation operation:

(++) :: [a] -> [a] -> [a]

[] ++ ys
= ys

(x:xs) ++ ys = x:(xs ++ ys)

The definition uses pattern matching on the first argument but not on the second. The second equation for
(++)
is very succinct and requires some thought, but once you have got it, you have understood a lot about how lists work in functional programming. Here is a simple evaluation sequence:

[1,2] ++ [3,4,5]

=
{notation}

(1:(2:[])) ++ (3:(4:(5:[])))

=
{second equation for
++
}

1:((2:[]) ++ (3:(4:(5:[]))))

=
{and again}

1:(2:([] ++ (3:(4:(5:[])))))

=
{first equation for
++
}

1:(2:(3:(4:(5:[]))))

=
{notation}

[1,2,3,4,5]

As this example suggests, the cost of evaluating
xs++ys
is proportional to the length of
xs
, where

length :: [a] -> Int

length []
= 0

length (x:xs) = 1 + length xs

Note also that

We know nothing about the first list, but we do know that the second list begins with
1
followed by
2
.

Concatenation is an associative operation. Thus

(xs ++ ys) ++ zs = xs ++ (ys ++ zs)

for
all
lists
xs
,
ys
and
zs
. We will see how to prove assertions like these in
Chapter 6
.

Three very useful list operations that we have met already are
concat
,
map
and
filter
. Here are their definitions using pattern matching:

concat :: [[a]] -> [a]

concat []
= []

concat (xs:xss) = xs ++ concat xss

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

map f []
= []

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

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

filter p
[] = []

filter p (x:xs) = if p x then x:filter p xs

else filter p xs

There is a common theme underlying these definitions that we will identify and exploit in
Chapter 6
. An alternative definition of
filter
is

filter p = concat . map (test p)

test p x = if p x then [x] else []

With this definition,
filter p
is implemented by converting each element of the list into a singleton list if it satisfies
p
, and the empty list otherwise. The results are then concatenated.

Two basic facts about
map
are that

The first equation says that applying the identity function to each element of a list leaves the list unchanged. The two occurrence of
id
in this law have different types: on the left it is
a -> a
and on the right it is
[a] -> [a]
. The second equation says that applying
g
to every element of a list, and then applying
f
to every element of the result, gives the same list as applying
f . g
to every element. Read from right to left, the equation says that two traversals of a list can be replaced by one, with a corresponding gain in efficiency.