It is reasonable to ask why you should learn yet another programming language. For example you may feel that you are already an excellent C++ programmer and there will be nothing to be gained by learning yet another programming language. In order, to compare functional programming with the imperative style of programming let consider a little example (essentially from the Haskell home page):

qsort [] = []

qsort (x:xs) = (qsort [y | y <- xs, y < x]) ++ [x] ++ (qsort [y | y <- xs, y >= x])

qsort( a, lo, hi ) int a[], hi, lo;

{

int h, l, p, t;

if (lo < hi) {

l = lo;

h = hi;

p = a[hi];

do {

while ((l < h) && (a[l] <= p))

l = l+1;

while ((h > l) && (a[h] >= p))

h = h-1;

if (l < h) {

t = a[l];

a[l] = a[h];

a[h] = t;

}

} while (l < h);

t = a[l];

a[l] = a[hi];

a[hi] = t;

qsort( a, lo, l-1 );

qsort( a, l+1, hi );

}

}

The advantages of programming in a functional language such as Haskell are:

- increased programming productivity (Ericsson measured an improvement factor between 9 and 25 in one set of experiments).
- shorter, clearer,
*more reliable*, and*more maintainable*code. - a smaller "semantic gap" between what is intended and the code (to actually achieve the intention).
- faster production of software.

Further reading in this area is the classic paper of John Hughes: why functional programming matters.

Functional languages are

Haskell is the leading lazy functional language. A variety of application packages have been written for it ... which hopefully we will explore during the course of the semester.

Functional languages are based on the lambda calculus: during the course of the semester we will explore the theory of this calculus by writing Haskell programs to implement various aspects of this theory. One particularly important aspect of the use of the lambda calculus in practice is the Hindley-Milner type system. One of the main exercises will be to develop a parametric type checker for the typed lambda calculus.

GETTING STARTED IN HASKELL: HUGS

You first task is to get started in Haskell: I am going to cover the start of the text by Hudak in short order and you are required to read along and fill out the lecture material as we go -- as you should have already had considerable programming experience: the introductory chapters should be relatively straightforward to follow. There are various other introductory sources in particular the gentle guide to Haskell 98 may be useful to you.

We shall be using the HUGS system which should be available to you on any of the Computer Science systems. If you have any difficulty let me and the software staff know. HUGS is a Haskell interpreter which works by loading files ( the

When you start up the HUGS system it reads in the standard prelude. It is worth looking at this file as it tells you what functions are already available but also gives some good examples of how to write Haskell code: you will find the file at

Perhaps one of the most delightful aspects of functional programming is use of patterns to express what must be done. To illustrate this consider the problem of appending two lists:

Lists are defined in the prelude and take one of two forms : the empty list

append:: ([a],[a]) -> [a]

append([],ys) = ys

append(x:xs,ys) = x:(append(xs,ys))

This definition starts with a specification of the
type of the append function: the way I have written *append* here
takes in a pair of lists of some type *a* (a variable type)
and produces a single list of the same type. The next two
lines specify the function: this is done by considering the two
possibilities for the first argument and describing what happens in
each case. This is often called a definition by structural
recursion as we break down
the structure of the first argument. When the first argument is
the empty list the function returns the second argument, while if
the first argument is a non-empty list we must recurse on the tail of
the
list in the expected manner.

The system evaluates this function by trying each pattern in turn until it finds the first one which matches. It then applies the transformation suggested by the RHS of that pattern. This does mean that the* order* in which patterns are written is important.

Functional programs are all about using (defined) functions within other functions. Here is a little example: to reverse a list we can use the*append* function above:

Curried programs:

I have written all the above programs in uncurried form: thus, if a function needs two arguments I have passed them in as a tuple. However, functional languages are better suited to defining functions in a curried form. This means that one would tend to define* append* as follows:

where the type* [a] -> [a] -> [a]* (which
should be read as *[a] -> ([a] -> [a]) *-- the
association is to the right) says the function takes in an element of *[a]*
and produces a function *[a] -> [a]*. This means we
should read *append x y* as *(append x) y* with association
to the left! Intitially these conventions may seem a little
confusing but they are conventions which are well-established and they
do, overall, reduce the need for parentheses. However, this does
mean that when you intend to first apply *f* to *x* then *g*
to the result you must use parentheses (see also the composition
notation) to get the desired effect:

*append [1,2,3]:: [Integer] -> [Integer]*

notice here the type is specialized as the first argument determines that the general type must be an integer.

Here is a program listing for the programs above and some others I discussed in class.

**Datatypes:**

One of the most convenient features of a functional programming language is its datatype definitions. These allow one to declare complex datatypes efficiently and to use them in a very convenient way. We have already used the list datatype so let us illustrate how one can write an insertion into a binary search tree. First it is necessary to define the datatype of binary search trees:

*Tip* and *Snode*
are called constructors. Their types are as follows:

*insert:: Ord a => a -> (STree a) -> (STree a)*

insert a Tip = Snode(Tip,a,Tip)

insert a (Snode(t1,b,t2))

| a < b = Snode(insert a t1, b, t2)

| a = b = Snode(t1,b,t2)

| a > b = Snode(t1,b,insert a t2)

The system evaluates this function by trying each pattern in turn until it finds the first one which matches. It then applies the transformation suggested by the RHS of that pattern. This does mean that the

Functional programs are all about using (defined) functions within other functions. Here is a little example: to reverse a list we can use the

This is an O(n^2) reverse (naive reverse) but it does express clearly the intention of reversing a list! Here is an O(n) reverse:reverse:: [a] -> [a]

reverse [] = []

reverse (x:xs) = append(reverse xs,[x])

This code is marginally less clear: note the use of a local definition to introduce the second argument. More on reverse!rev:: [a] -> [a]

rev xs = rev1 (xs, [])

where rev1 ([], ys) = ys

rev1 (x:xs, ys) = rev1 (xs,x:ys)

Curried programs:

I have written all the above programs in uncurried form: thus, if a function needs two arguments I have passed them in as a tuple. However, functional languages are better suited to defining functions in a curried form. This means that one would tend to define

append:: [a] -> [a] -> [a]

append [] ys = ys

append (x:xs) ys = x:(append xs ys)

where the type

Using the curried form does mean that the function with just one argument applied is a valid term:g (f x)notg f x = (g f) x.

notice here the type is specialized as the first argument determines that the general type must be an integer.

Here is a program listing for the programs above and some others I discussed in class.

One of the most convenient features of a functional programming language is its datatype definitions. These allow one to declare complex datatypes efficiently and to use them in a very convenient way. We have already used the list datatype so let us illustrate how one can write an insertion into a binary search tree. First it is necessary to define the datatype of binary search trees:

Here we have actually also required that the elements in the binary search tree must admit an order.data Ord a => STree a

= Tip

| Snode (STree a,a,STree a)

This allows us to define an insertion as follows:tip:: () -> STree(a)

Snode:: (STree a,a,STree a) -> STree a

insert a Tip = Snode(Tip,a,Tip)

insert a (Snode(t1,b,t2))

| a < b = Snode(insert a t1, b, t2)

| a = b = Snode(t1,b,t2)

| a > b = Snode(t1,b,insert a t2)

Notice that we may use the pattern matching for arbitrary datatypes by indicating the constructor involved. Notice also we have used

Here is a program listing for an implementation of red/black trees.

Here is a program listing for the programs above and some others I discussed in class.

This says that any type belonging to the equality class has defined two functions calledclass Eq a where

(/=), (==) :: a -> a -> bool

x /= y = not(x == y)

instance (Eq a) => Eq (STree a) where

Tip == Tip = True

SNode (t1,a,t2) == SNode(s1,b,s2) = (t1 == t2) && (a == b) && (t2 == s2)

This says that

Once one has the equality class one can write functions which apply to any type in that class: for example sorting algorithms will apply to types which are in the Ord class:

Here is a little example of how one might write the set equality predicate:sort:: Ord a => [a] -> [a]

Now this function can be greatly improved if one has ordered lists: try to write a more efficient set equality test under the assumption that the lists are always sorted:seteq:: Eq a => [a] -> [a] -> bool

seteq xs ys = (subset xs ys) && (subset ys xs) where

subset [] ys = True

subset (x:xs) ys = (member x ys) && (subset xs ys) where

member x [] = False

member x (y:ys)

| x == y = True

| otherwise = member x ys

setordeq:: Ord a => [a] -> [a] -> bool

List comprehension:

Another nice facility that Haskell has, which was originally introduced into Miranda by David Turner, is list comprehension. As we shall discover this is linked to another important concept namely

Here is an example of its use: suppose we want to find all the Pythagorean triples less than 100 then we could write:

It really makes the code close to a specification. But what is happening under the hood? List comprehensions are translated out by the system using the following steps:pythag: Integer -> [(Integer,Integer,Integer)]

pythag n = [ (x,y,z) | x <- [1..n], y <- [1..n], z <- [1..n], pyth (x,y,z)] where

pyth (x,y,z) = x * x + y * y == z * z

List comprehensions allow the very succinct and straight forward definition of the quicksort algorithm:[ e | ] = [ e ]

[ e | x <- xs , r] = flattten (map f xs) where

f x = [ e | r ]

[ e | p, r ] = if p then [ e | r ] else []

qs: Ord a => [a] -> [a]

qs [] = []

qs (a:as) = (qs [x| x <- as, x<a]) ++ [a] ++ (qs [x| x <- as, x>as])

As mentioned above Haskell's list comprehension is a specialization of the more general monad

facilities of Haskell. Monads, in fact, are an essential part of the Haskell language as all IO is managed through the IO-monad.

So what is a monad?

Ernie Manes) they consist of:

- A type constructor
*T* - A function
*return :: a -> T a* - A sequencer
*(>>=) :: T a -> (a -> T b) -> T b*

There is a special "do" syntax for monads which makes them much more convenient to use:instance Monad [ ] where

return x = [x]

[] >>= q = []

(x:xs) >>= q = (q x)++(xs >>= q)

do { r } = rHere is the quicksort function written using this syntax:

do { x <- p ; C ; r } = p >>= q where q x = do { C ; r }

do { r' ; C ; r } = r' >>= \_ -> ( do { C ; r } )

Here is an example of the use of the exception monad for evaluating based numbers. Theqs [] = []

qs (x:xs) = (do xl <- xs

if x1 < x then return x1 else [])

++ [x] ++

(do x2 <- xs

if x2 >= x then return x2 else [])

difficulty with conventional code is that, if the base is octal, and the digits 8 or 9 are used then we must raise an exception which has to be propogated throughout the program. In conventional code this would mean that one would have to have code to propogate the exception in the correct manner. The code using the "do" syntax hides this nicely.

The above example is nice except for the fact that Haskell already has an exception handling capability in the

In order to be a "reasonable" monad (which behaves in a reasonable manner) the functions involved in the definition of a monad should satisfy various identities. First, if

so that every monad is necesarily in the functor class. Furthermore we can define anotherinstance Monad T => Functor T where

fmap:: (a -> b) -> (T a -> T b)

fmap f p = p >>= (\x.return (f x))

important map:

with respect to these maps the following identities:mult :: Monad T => T(T a) -> T a

mult xx = xx >>= \x.x

unit :: Monad T => a -> T a

unit = return

The standard presentation of a monad is in fact this: a type constructor with a unit and a multiplication satisfying the above identities.mult . mult = mult . fmap mult :: T(T(T a)) -> T a

mult . unit = mult . fmap unit = \x.x :: T a -> T a

However, these maps can also be used to obtain what is called a Kleisli triple presentation:

and the identites can be re-expressed using this form as:return = unit

p >>= q = mult (mapf q p)

(\x -> unit x >>= (\x.x)) = (\x.x >>= unit) = (\x.x) :: T a -> T a

(p >>= q) >>= r = p >>= (\x . q x >>= r) :: T c