A Quick Overview of Haskell^{∗}

D.B. Carpenter

September 16, 1993

1 About functional languages

Functional programming languages are very mathematically “pure”. They have no intrinsic idea of control-flow, store, assignment, etc. A functional program is a mathematical expression. This expression may be a function—say from inputs to outputs.

Higher order functions (functions which take other functions as parameters, or return other functions as results) can be used freely. In practise this allows imperative control-flow to be emulated, if necessary.

Lazy evaluation permits manipulation of “infinite” data structures, in particular infinite lists. These provide an alternate means of representing state transition— the history of a transition system is an infinite list (stream) of system states.

So we can recover sequential programming if desired (usually not), and also model more general imperative paradigms, including process parallelism, easily.

Beyond that, functional language are very uniform, and free of ad hoc restrictions. This makes them very expressive, and allows high levels of abstraction.

2 Some basic types

The Haskell system comes with a large number of predefined types (including Int, Integer, Bool, Char, Float, complex types, etc). A constant can be specified to have a particular type by a declaration

  a :: Int

A function type is a type like any other

∗Slides presented at the Southampton CCG seminar, 27th January 1993

f :: Int -> Float

means f a function from Int to Float. Functions can take functions as arguments, or return functions as results

g :: (Int -> Float) -> Float
h :: Int -> (Int -> Float)
h :: Int -> Int -> Float

Multiple arguments represented by “currying”. The two signatures of h are equivalent by definition and represent a function from an Int to a Int -> Float— aka a function from two Ints to a Float. Another basic type is the tuple

a :: (Int, Float)
b :: (Int, Int, Int)

A function from a pair to a float:

h' :: (Int, Int) -> Float

3 Function application—expressions

Function application represented by juxtaposition

f 3
g f
h 3 4
h' (3, 4)

Functions of two arguments can be used as “infix” operators

(+), (*) :: Float -> Float -> Float

(obviously these are predefined and overloaded in practise) so arithmetic expressions can be written in familiar ways (and other function applications can be written in unfamiliar ones)

3.0 + (4.0 * f 3)
3 `h` 4

Due to currying, functions can be partially applied

  h 3

is a function from Int to Float, and

  (2.0 *)

is a function from Float to Float. (These are elementary examples of functionvalued expressions).

4 Data constructor function definition

“Algebraic types” are roughly equivalent to “variant records” or “Unions” in some languages. They have an associated set of “constructor functions”, which are genuine functions, but with limited power.

  data IntList = Node Int IntList | Nil

defines an algebraic type IntList with two constructor functions Node and Nil. Node is of type Int -> IntList -> IntList. Nil is a constant (“function of zero arguments”) of type IntList.

The following expressions are of type IntList

  Nil
  Node 1 (Node 2 (Node 3 Nil)))
  1 `Node` Nil

Not surprisingly, Haskell has built in syntax for representing general lists—this is just given as an example of algebraic types.

5 General function definition

General functions are defined by a straightforward syntax

  double :: Float -> Float
  double x = 2.0 * x
  factorial :: Int -> Int
  factorial n = if n == 0
                  then 1
                  else n * factorial (n - 1)

Functions on algebraic types are handled by “pattern-matching”

  isEmpty :: IntList -> Bool
  isEmpty (Node x xs) = False
  isEmpty  Nil        = True
  car :: IntList -> Int       -- ``head''
  car (Node x xs) = x
  cdr :: IntList -> Intlist   -- ``tail''
  cdr (Node x xs) = xs

Note car and cdr are undefined if the argument is Nil.

double could also be defined by

  double = (2.0 *)
  double = (\x -> 2.0 * x)

6 Special syntax for lists

Lists can be defined from scratch—a restricted form (Ints only) was already given. They are used so commonly that some special syntax has been added to the language. The equivalent of Node is (:), and it’s normally used as an infix function. The equivalent of Nil is []. Additionally a list of several items can be written as comma-separated sequences in square brackets. The following are equivalent:

  (:) 1.0 ((:) 2.0 [])
  1.0 : (2.0 : [])
  [1.0, 2.0]

This is a list of two Float items. Its type is written: [Float]. This is an example of a parametrised type—in this case the parameter type is Float.

A “list comprehension” is another special piece of syntax for building lists. A simple example is the expression

  [x^2 | x <- xs]

Here xs is a list of numeric values. The result of the expression is a list formed by instantiating x to the value of each item in xs, and computing the expression preceding the |. If xs = [1, 2, 3], the result of the above expression is [1, 4, 9]. (Fortran users might interpret this as something like an implied do loop!) This syntax has a few extensions—multiple generators can be placed after the | (nested implied do loop!), and predicates can be added to filter out certain values of the “dummy indices”.

7 Normal order evaluation

Lazy languages implement “normal order evaluation” of expressions. Evaluation of an expression starts “at the outermost level”, and no sub-expression is evaluated unless it is actually needed. Eg, if we had

  cond :: Bool -> a -> a -> a
  cond True  x y = x
  cond False x y = y
  n = 0

then the expression cond (n /= 0) (1 / n) 0 is well-defined. Only the first argument has to be evaluated to make the pattern-match.

8 Infinite data structures

This means that we can deal in expressions which would take ∞ly long to evaluate in full, so long as we only choose to look at a parts of the result which can be evaluated in finite time. It often simplifies construction of data structures if one doesn’t worry initially about termination.

An application of infinite lists is in modelling state transition. Define

  process :: (s -> e -> s) -> s -> [e] -> [s]
  process trans st ~(env:envs) =
        st : process trans (trans st env) envs

This takes: a transition function from a state and a current “environment value” to a new state; an initial state; and an ∞ list of successive environment values. It returns an ∞ list of states.

As an example, take the “transition function” to be (+). This adds the current value of the “environment” to the current value of the “state”. Then we would have

  process (+) 0 [1, 3, 5, 7, ...]  ==
                        [0, 1, 4, 9, 16, ...]

So long as the computation only ultimately requires a finite number of items from this list, the fact that it formally contains an ∞ number of items doesn’t matter.

9 Some standard functions

Some standard functions:

  map f xs
     = [f x | x <- xs]
  zipWith f [x, y, ...] [a, b, ...]
     = [f x a, f y b, ...]
  transpose [[a1, a2, ...], [b1, b2, ...], ...]
     = [[a1, b1, ...], [a2, b2, ...], ...]
  (f . g) x
     = f (g x)

All these can easily be defined in terms of the operations given so far (and are so-defined in the prelude). Where they take lists, all of them are applicable to finite or infinite lists.

10 Haskell arrays

An array can be constructed from an “association list”. An association is a pair constructed with the infix data constructor (:=), binding a subscript to a value. array is a function which takes a pair of bounds and an association list, and returns an array. Eg

  a = array (1, 3) [1 := Red,
                    2 := Blue, 3 := Green]

is an array with subscript type Int (tuples are also allowed, providing multidimensional arrays) and values in some algebraic type representing colours. The subscripting operator is the infix function (!), so

  a ! 2  ==  Blue

Arrays aren’t “primitive” in Haskell. They can be implemented (inefficiently) in terms of function. They don’t even have any special syntax, as lists do. So it’s possible to implement ones own array system (provided efficiency isn’t a overiding concern).