HacWrite - 8 A brief introduction to Haskell

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:

Haskell uses layout (indentation) rather than delimiting character to separate declarations, branches in case expressions, etc.
Anonymous functions are written using \ and ->: for example, \ x -> x is the identity function.
The operator . is function composition.
The operator $ is just function application, that is f $ x = f x. It is right associative and has low precedence, so it can be used to avoid nested parentheses. We often write expressions like
```
f $ g $ h $ \ x -> x + 1
```
instead of
```
f (g (h (\x -> x + 1)))
```
An ordinary alfanumeric identifier can be used as an infix operator by enclosing it in back quotes. We sometimes write, for example,
```
f x `ap` y
```
instead of
```
ap (f x) y
```
Infix operators are turned into functions that can be passed as arguments by enclosing parentheses. For example, (*) is equal to \x y -> x * y.
Operators can be partially applied using sections, again using parentheses. For example, (2/) is the function \x -> 2 / x, and (/2) is the function \x -> x / 2.
The Haskell syntax for tuples, lists and functions is chosen so that a type and the values of the type look similar. For example, the type of the tuple (3,False,"fudget") is (Int,Bool,String), the type of the list [1,2,3] is [Int] and the type of the function \ x -> x is a -> a.
In type expressions, names starting with lower case letters are type variables and names starting with upper case letters are type constructors.
We often use the Haskell standard type Either for disjoint unions, defined as
```
data Either a b = Left a | Right b
```
and the type Maybe for optional values, defined as
```
data Maybe a = Nothing | Just a
```
The result of a Haskell program is the value bound to the identifier main. This value should be a representation of the effect (as discussed in Chapter 3) the execution of the program should have on the outside world. A program can be as simple as
```
main = print "Hello, world!"
```

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 x₁ <- m₁
   x₂ <- m₂
   ...
   m_n

is defined to mean the same as

m₁ >>= (\ x₁ ->
m₂ >>= (\ x₂ ->
...
m_n))