Headline

A form of list without basic operations for mutation

Description

An immutable list is a data structure for lists (ordered sequences) of elements of a common type. An immutable list can be manipulated in a basic sense like this:

• Observations
  • Determine whether the list is null (i.e., empty).
  • Retrieve the head of the list, if it exists (i.e., the first element of the list)
  • Retrieve the tail of the list, if it exists (i.e., the rest or all but the head of the list).
• Construction
  • Construct a nil list (i.e., the empty list).
  • Construct a cons list (i.e., a non-empty list from given head and tail).

• Adding an element in ways other than by using cons.
• Removing an element in ways other than by using tail.

Illustration

Immutable lists in Haskell

Here are some lists with an increasing number of elements:

[]
[1]
[1,2]
[1,2,3]

We showed convenience notation for list construction. Fundamentally, lists are constructed from two constructor functions: nil (square brackets) and cons (colon). Let us construct the same lists with the fundamental constructors:

[]
1:[]
1:(2:[])
1:(2:(3:[]))

These are the functions to retrieve the head and the tail of a list:

head :: [a] -> a
tail :: [a] -> [a]

(In reality, these functions have more general types, but let's simplify things here.)

Here are some applications of head and tail:

> head [1,2]
1
> tail [1,2]
[2]

Here is how we test a list to be empty:

null :: [a] -> Bool

For instance:

> null []
True
> null [1,2]
False

Further operations on lists can be expressed in terms of the operations described so far. Let us define an operation snoc for adding an element at the end of a list. (snoc is inverse of cons in that cons adds an element at the start of a list.) Here is the function definition:

snoc :: [a] -> a -> [a]
snoc [] x = [x]
snoc (x:xs) y = x : snoc xs y

Here is an illustrative function application:

> snoc [1,2] 3
[1,2,3]

The function definition for snoc is representative for functions on lists in that we leverage pattern matching with two cases: one for the empty list, another one for nonempty lists. Further, we leverage recursion: the function snoc is defined in terms of itself; the first equation is the base case for recursion.

Headline

The use of self-reference in defining abstractions

Illustration

Clearly, there are different forms of recursions, as they are different abstraction mechanisms that permit recursion. For instance, in functional programming, both Functions and data types may be defined recursively.

Recursive functions

Consider the following recursive formulation of the factorial function in Language:Haskell:

-- A recursive definition of the factorial function
factorial n =
  if n==0
    then 1
    else n * factorial (n-1)

This is essentially a form of primitive recursion: the function definition checks for the argument n to be "0" for the base case and applies the function recursively to the predecessor of the argument otherwise. For the record, non-recursive formulations are feasible, too, depending on the helper functions we are willing to use. For instance, we may use the ".." operator to enumerate all values in a range and then apply the product function:

-- A non-recursive definition of the factorial function
factorial' n = product [1..n]

Headline

Matching values against patterns to bind variables

Description

Pattern matching may be concerned with different kinds of types, e.g., text or trees. In the case of text, regular expressions provide the foundation for patterns. In the case of trees and specifically in the context of functional programming, algebraic data types provide the foundation for patterns; in this case, pattern matching is concerned with case discrimination on different constructor patterns such that variables are bound in successfully matched patterns for use in expressions.

Illustration

Pattern matching in Haskell

The basics of Haskell's pattern matching are very similar to those of other functional programming languages.

Pattern matching on pairs

-- Project a pair to first component
fst :: (a,b) -> a
fst (x,_) = x

-- Project a pair to second component
snd :: (a,b) -> b
snd (_,x) = x

These two functions fst and snd are defined like this (or similarly) in the Prelude module of Language:Haskell. They are defined by pattern matching on the structure of tuples; see the the left-hand sides of the function definitions. The idea of such pattern matching is of course that variables in the pattern (on the left-hand side) can be used in the expression of the definition (on the right-hand side).

Pattern matching on lists

-- Retrieve head (first element) of a list
head :: [a] -> a
head (x:_) = x

-- Retrieve tail (all but first element) of a list
tail :: [a] -> [a]
tail (_:xs) = xs

These two functions head and tail are defined like this (or similarly) in the Prelude module of Language:Haskell. They demonstrate that non-empty lists are constructed with the cons constructor ":" from a head and a tail.

Pattern matching is particularly convenient, when functions should be defined by case discrimination on the different constructor patterns for a data type. Consider, for example, the length function (again borrowed from the Prelude); this definition consists of two equations: one for the case of an empty list and another case for non-empty lists:

-- Determine length of list
length :: [a] -> Int
length [] = 0
length (_:xs) = length xs + 1

Other forms of pattern matching

• Pattern matching is particularly useful for user-defined algebraic data types.
• Pattern matching is not limited to the use on left-hand sides of equations. Instead, pattern matching can also be performed through case expressions in an expression context.
• Haskell patterns may involve so-called guards to control the selection of equations (cases) not just purely on the grounds structure but also computations on top of bound variables.
• Haskell provides different forms of patterns to deal with laziness. This is not further discussed here.