8 A brief introduction to Haskell

The purely functional programming language that we will use in the rest of the thesis is Haskell [Pet97]. An introduction can be found at [HPF97], and there are also two reports that define the language and its standard libraries [PH97b][PH97a].

We believe that the program examples will be readable without detailed knowledge of Haskell--familiarity with some functional language is hopefully sufficient. However, some recurring patterns are perhaps worth explaining:

A unique feature of Haskell is the type class system [WB89], which is a systematic treatment of overloading. A type class declaration introduces a number of functions that will be overloaded. An instance declaration gives definition of the overloaded functions for a particular type. For example, a standard type class in Haskell is the class for types that support equality:

class Eq a where
   (==) :: a -> a -> Bool
To allows boolean values to be tested for equality with the == operator, an instance declaration like the following can be used:

instance Eq Bool where
  True   == True   = True
  False  == False  = True
  _      == _      = False
For some standard type classes, instance declarations can be generated automatically by adding a deriving clause to the type definition:

data Bool = False | True deriving Eq
When an overloaded function is used in a new function definition, the overloading may be inherited by the new function. For example, consider the function elem that checks if a value occurs in a list, defined as

x `elem` [] = False
x `elem` (y:ys) = x==y || x `elem` ys
The type of elem is written

elem :: Eq a => a -> [a] -> Bool
where the part Eq a => is called a context. It means that the type variable a is restricted to range over types that are instance of the Eq class.

In Haskell 1.3, the class system was generalised to allow classes of type constructors [Jon93] instead of just classes of base types. Type variables were extended to range over type constructors. This means a that type scheme like a Int is allowed. The type variable a can be instantiated to, for example, Maybe and the list type constructor, giving the types Maybe Int and [Int], respectively.

The well known function map,

map :: (a->b) -> [a] -> [b]
which is defined for lists in many functional languages, can now be generalised by introducing the class Functor,

class Functor f where
   map :: (a->b) -> f a -> f b
Instances for the lists and the Maybe type can be defined as

instance Functor [] where
   map f []      = []
   map f (x:xs)  = f x : map f xs

instance Functor Maybe where
   map f Nothing   = Nothing
   map f (Just x)  = Just (f x)
However, the introduction of constructor classes was motivated by the change to monadic I/O (see Section 41.1.3) and a convenient syntax for monadic programming. The class Monad is defined as

class Monad m where
  return  :: a -> m a
  (>>=)   :: m a -> (a -> m b) -> m b
and the special do syntax for monadic expressions,
do x1 <- m1
   x2 <- m2
is defined to mean the same as

m1 >>= (\ x1 ->
m2 >>= (\ x2 ->