Haskell makes a distinction between operators and functions;
the main difference is that opertors have infix syntax
(and their names consist of special symbols +,
*, <, etc.),
whereas functions have prefix syntax.
It is possible to convert operators to functions by enclosing
them in brackets, for example, (+) is a function
of type
Int -> Int -> Int
and (++) is a function of type
[a] -> [a] -> [a]
These functions are then applied using prefix notation;
for example,
(+) 2 3
(which will evaluate to 5).
As these are functions, they can be applied to just one argument;
for example,
(*) 2
is a function of type Int -> Int
which takes a number as argument and returns twice that number.
A possible definition of the twice function that we
looked at in the first lectures is therefore
-- function to double a number twice :: Int -> Int twice = (*) 2 |
Note that we don't use a formal parameter in this definition!
When we apply twice to a number (say 6),
the interpreter will evaluate the function as follows:
twice 6 => (*) 2 6
=> 2 * 6
=> 12
|
I.e., twice is simply replaced by its definition (*) 2.
Haskell provides a syntax for partially-applied operators (i.e., for
operators that aren't given their full number of arguments), which
involves writing the operator and one of its arguments in brackets,
for example, (*2) is equivalent to (*) 2.
Partially-applied operators like this are called sections,
and are treated as functions by the Haskell interpreter.
For example, (++".") is a function of type
[Char] -> [Char]
(it takes a string as argument and adds a dot to the end of the string).
Similarly, ([0]++) is a function of type
[Int] -> [Int]
that takes a list of numbers and adds 0 to the start of
the list;
in fact, this function can also be written as (0:).
Suppose we want to double every element in a list of numbers; that is we want to define a function
doubleAll :: [Int] -> [Int]
with the desired behaviour.
Using a list comprehension,
we might write:
-- function to double every number in a list of Ints doubleAll :: [Int] -> [Int] doubleAll ns = [ 2*n | n <- ns ] |
which is a satisfyingly simple definition. Suppose we also want to compute the factorial of every number in a list; then we might define another function:
-- function to compute the factorial of -- every number in a list of Ints factAll :: [Int] -> [Int] factAll ns = [ fact n | n <- ns ] |
where fact has been
defined earlier.
And supposing we also want to compute the sum of every list in a list
of lists of numbers, we might further define:
-- function to compute the sum of -- every list in a list of lists of Ints sumAll :: [[Int]] -> [Int] sumAll nss = [ sum ns | ns <- nss ] |
where sum is the predefined Haskell function
that adds all the numbers in a list.
All the functions above follow a similar pattern, and since we use this pattern so often, it might occur to us to abstract this pattern in the interests of code reuse. We are thus led to define a polymorphic function
-- apply a function to every element in a list map :: (a -> b) -> [a] -> [b] map f l = [ f x | x <- l ] |
or, equivalently,
map f [] = [] map f (x:xs) = (f x) : map f xs |
In fact, the map function is predefined in Haskell,
and we can simply define the functions above by:
doubleAll = map double
where double x = 2*x
factAll = map fact
where
fact x
| x <=0 = 0
| otherwise = x * fact (x-1)
sumAll = map sum
|
Note that using map aids modularity, in that
our definitions need only concentrate on sub-problems
(e.g., the local definitions above).
Suppose we want to multiply all the numbers in a list together; we can define a Haskell function to do this as follows:
product :: [Int] -> Int product [] = 1 product (x:xs) = x * product xs |
and suppose we want to "flatten" a list of lists into a list by concatenating all the lists in the lists of lists; an appropriate Haskell definition is:
flatten :: [[a]] -> [a] flatten [] = [] flatten (l:ls) = l ++ flatten ls |
An interesting pattern emerges when we examine how these functions are evaluated. For example,
product (1 : (2 : (3 : (4 : (5 : [])))))
= 1 * (2 * (3 * (4 * (5 * 1))))
|
and
flatten ([1,2] : ([3,4,5] : ([] : ([6] : []))))
([1,2] ++ ([3,4,5] ++ ([] ++ ([6] ++ []))))
|
The effect of each of these functions is to replace the cons operator
(:) with another operator (* or ++)
and to replace the empty list ([]) with another value
(1 in the case of product, and
[] in the case of flatten).
In other words, these functions replace the list constructors with
other operators (or, in general, functions).
We call such functions
catamorphisms.
To abstract on this pattern, we require a function (let's call it
cataList that takes as
arguments:
f to replace cons, a value e to replace
the empty list, and a list l), we get an expression
cataList f e l
which should evaluate to the result
of replacing cons (:) with f and []
with e in the list l.
For example, product l will be
cataList (*) 1 l
and flatten l will be
cataList (++) [] l
We define cataList as follows:
cataList f e [] = e cataList f e (x : xs) = f x (cataList f e xs) |
In fact, Haskell has a predefined function that is defined in this way
(it's called foldr rather than cataList),
so we can define
product = foldr (*) 1 flatten = foldr (++) [] |
A polynomial in a variable x is a sum of powers of x;
that is, it's an expression such as
3*(x^4) + 4*x + 6
or
x^4 + 2*x^3 + x + 1
(it's standard practice to write the powers of x
in decreasing order).
The general form of a polynomial is
a*x^n + b*x^(n-1) + ... + c*x^1 + d*x^0
where the numbers a..d are called
coefficients.
For example, the polynomial
5*x^4 + 2*x^3 + x + 2
is equal to
5*x^4 + 2*x^3 + 0*x^2 + 1*x^1 + 2*x^0
and the coefficients are 5,2,0,1,2.
As this example suggests, a polynomial can be represented
by a list of its coefficients:
given the list [5,2,0,1,2] of coefficients, we can work out
that the represented polynomial is that given above.
Moreover, given a value for x, we can replace x
withthat value and compute the value of the polynomial expression.
For example, if we replace x with 3 in the
polynomial above, we get the value:
5*3^4 + 2*3^3 + 0*3^2 + 1*3^1 + 2*3^0
=
5*81 + 2*27 + 0 + 3 + 2
=
405 + 54 + 3 + 2
=
464
We now define a function
poly :: Int -> [Int] -> Int
that takes a value (for x) and a list of coefficients,
and computes the value of the polynomial, as illustrated above.
For example, we will define the function so that
poly 3 [5,2,0,1,2] = 464 .
We begin by attempting a recursive definition using pattern-matching:
poly x [] = ?
poly x (c:cs) = ??
For the base case, if the list of coefficients is empty,
then we want to compute the sum of the empty sequence of powers of
x, so it makes sense to choose 0
for the right-hand side of the first equation
(cf. factorials).
poly x [] = 0
What should we write for the right-hand side of the second equation?
Let's consider applying poly x (whatever x is)
to the list of coefficients [5,2,0,1,2].
This list matches the pattern c:cs with c
bound to 5 (the head of the list) and cs
bound to [2,0,1,2] (the tail of the list).
If we define our function correctly, a recursive call poly x cs
will evaluate to
2*x^3 + 0*x^2 + 1*x^1 + 2*x^0 .
All we have to do is add 5*x^4 to this to get the desired
result for poly x [5,2,0,1,2], so we might write
(recalling that c is bound to 5, the head
of the list):
poly x (c:cs) = c*x^??? + poly x cs
What power should we raise x to?
We can't write the constant 4 otherwise x
would always be raised to the fourth power, and we'd have
poly 3 [5,2,0,1,2]
=
5*3^4 + 2*3^4 + 0*3^4 + 1*3^4 + 2*3^4
(as an exercise, check this by going through a step-by-step evaluation).
Note that the powers of x decrease by one in each
summand of the polynomial, and that the length of the list of
coefficients decreases by one on each recursive call of poly.
We can see that the power to which we raise x is always
one less than the length of the list of coefficients.
Since the length of cs is one less than the length of
c:cs a correct definition is:
poly x (c:cs) = c*x^(length cs) + poly x cs
Although the definition is correct, it's rather inefficient.
For each call of poly x, we evaluate the length of the list
of coefficients.
The length function is recursive, and its evaluation
takes roughly the same number of steps as there are elements in the
argument list
(more precisely, the time taken to evaluate length l
is proportional to the number of elements in l).
To improve the efficiency of poly, we use the same
trick that we used in computing values in the Fibonnacci sequence
in an earlier lecture,
where we introduced an ancillary function fibs
that computed the nth and (n+1)th
values in the sequence.
Here, we introduce a function
polyLen :: [Int] -> (Int,Int)
that computes both the value of the polynomial and the length of
the list of coefficients; the idea is:
(*) polyLen cs = (poly x cs, length cs)and we can then define
poly x cs = p
where
(p,l) = polyLen cs
Our idea (*) gives a straightforward definition
for the base case:
polyLen [] = (poly x [], length [])
= (0,0)
For the recursive case, we use (*) to calculate:
polyLen (c:cs)
=
(poly x (c:cs), length (c:cs))
=
(c*x^(length cs) + poly x cs, 1 + length cs)
=
(c*x^l + p, 1+l)
where
(p,l) = polyLen cs
so we have arrived at the definition:
poly x cs = p
where
(p,l) = polyLen cs
polyLen [] = (0,0)
polyLen (n:ns) = (n*x^l + q, l+1)
where
(q,l) = polyLen ns
|
If we now define
addp n (q,l) = (n*x^l + q, l+1)
then we see that
polyLen = foldr addp (0,0)
So we can shorten our definition to:
poly x cs = p
where
(p,l) = foldr addp (0,0) cs
where
addp n (q,l) = (n*x^l + q, l+1)
|
foldl
Haskell also has a predefined function foldl
which is similar to foldr but "groups to the left"
(the names of the functions are abbreviations of
"fold left" and "fold right").
If we apply foldr (+) 0 to a list
1 : (2 : (3 : (4 : (5 : []))))
the result is
1 + (2 + (3 : (4 : (5 + 0))))
However, if we apply foldl (+) 0 to the same list,
we get:
((((0 + 1) + 2) + 3) + 4) + 5
Note that the brackets now group to the left, and that 0
also appears at the left.
In this case, where we fold with +, there is no
difference in the final result, because + is an
associative operator and it makes no difference where we put the
brackets in the sum of a sequence of numbers.
However, there is a difference in general, as can be seen by
comparing the types of the two functions:
foldr :: (a -> b -> b) -> b -> [a] -> b
foldl :: (b -> a -> b) -> b -> [a] -> b
The function can be defined as follows:
foldl f e [] = e
foldl f e (x:xs) = foldl f (f e x) xs
As an example, define
switch :: [a] -> a -> [a]
switch tl hd = hd : tl
Then a function to reverse a list is:
-- reverse a list
-- e.g., rev [1,2,3] = [3,2,1]
rev :: [a] -> [a]
rev = foldl switch []
where
switch tl hd = hd : tl
|
(see the exercises below).
We didn't specify the type of the function cataList.
The Haskell interpreter is able to infer the type of this function,
and we use foldr (Haskell's predefined cataList
function) to illustrate the procedure that the
interpreter follows in inferring the type of the function.
Consider the following definition:
foldr f e [] = e foldr f e (x : xs) = f x (foldr f e xs) |
We can see from both these equations that foldr takes
three arguments; the type of this function must therefore be of the
form
a -> b -> c -> d
where a is the type of the parameter f,
b is the type of the parameter e,
c is the type of the third parameter, and
d is the type of the result.
We can also see straight away that the third argument is a list
(because of the patterns in the definition); therefore, we know
that c is a list type, and will be of the form
[c1], where c1 is the type of the elements
in the list.
Therefore, we can make the type of foldr more precise;
it is of type:
a -> b -> [c1] -> d
From the first equation, we see that the type of e
is the same as the type of the result, because e
is the result in the first equation.
This means that the types b and d
must be the same; let's just use the name b for this
type, and improve our guess about the type of foldr to:
a -> b -> [c1] -> b
From the second equation, we see that the parameter f
is a function, because it is applied to an argument. In fact,
it is applied to two arguments, x and
foldr f e xs.
Therefore, the type of f must be of the form
a1 -> a2 -> a3
and a better approximation to the type of foldr is
therefore:
(a1 -> a2 -> a3) -> b -> c1 -> b
Recal that f was applied to x,
where x is a variable in the pattern of the second
equation, and represents the head of the list that is the third argument
to foldr;
this means that x has type c1, and therefore
the type of f's first argument is c1.
The type of f is therefore
c1 -> a2 -> a3
What about the type of its second argument?
The second argument is
foldr f e xs
so the type of this expression must be the return-type of foldr,
which we have called b.
Therefore, a more precise type for f is:
c1 -> b -> a3
The body of the second equation is
f x (foldr f e xs)
and so the type of this expression must be a3, the return-type
of f.
But this must also be the return-type of foldr, which is
b, so a3 and b must be the same;
again, we will call this type b, which means that the
type of f is
c1 -> b -> b
and the type of foldr is
(c1 -> b -> b) -> b -> [c1] -> b .
We now have types for all the subexpressions in the definition of
foldr; we can annotate this definition with the types
of all its subexpressions as follows:
foldr (f::c1->b->b) (e::b) ([]::[c1]) = e::b
foldr (f::c1->b->b) (e::b) ((x::c1) : (xs::[c1])
= (f::c1->b->b) (x::c1) (foldr (f::c1->b->b) (e::b) (xs::[c1]))
Now that we have types for all the subexpressions, the process of type-inference is
complete.
Or almost complete: we still have to check thath all function applications are
type-correct.
This means that wherever we see a function application such as g x,
where g has type, say, a -> b, we should check that
x has type a.
If this is the case, the function application is type-correct, and the type
of the expression g x is b.
It is straightforward to check that this is the case for the definition of
foldr, so we conclude that the definition is type-correct,
and that the type of foldr is
(c1 -> b -> b) -> b -> [c1] -> b .
Note that the types c1 and b are type variables,
so the function is polymorphic:
the variables c1 and b can be specialised to
particular types
(for example, in foldr (*) 1, both c1 and b
are specialised to Int).
Since these variables are just names, we can freely change them - the type we
have inferred becomes slightly more readable if we change the name
c1 to a:
foldr :: (a -> b -> b) -> b -> [a] -> b
rev,
give a step-by-step evaluation of rev [2,4,7].poly using foldl
instead of foldr.
5*x^4 + 2*x^3 + 0*x^2 + 1*(x^1) + 2*x^0
=
(((5*x + 2)*x +0)*x + 1)*x + 2
=
((((0 + 5)*x + 2)*x + 0)*x + 1) + 2