Unit 2: Lists
The most important datatype in any functional programming language is the list. A list is a linearly ordered collection of elements. All the elements of a list must be of the same type. The easiest way in which to specify a list is by enumeration: you simply write the elements of the list between square brackets and separate them with commas. Here are some examples with their types:
[3, 7, 5, 88] :: [Int] [[2, 3], [4, 8, 17]] :: [[Int]] ['t', 'i', 'm', 'e'] :: [Char] "time" :: [Char]
Note that the last two of these are equivalent.
The empty list, written
, belongs to type
Haskell has a means of producing lists of integers in arithmetical progression.
A few examples should make clear how this is achieved:
Prelude> [1 .. 10] [1,2,3,4,5,6,7,8,9,10] Prelude> [3, 5 .. 11] [3,5,7,9,11] Prelude> [(-9), (-7) .. (-3)] [-9,-7,-5,-3]
Because Haskell is a lazy functional programming language it can handle infinite lists. Here are some examples:
nats = [1 .. ] evens = [2, 4 .. ] negs = [(-1), (-2) .. ] ones = 1:ones stars = '*':stars
Haskell provides several list operators.
: (binary infix), which sticks an element at the front of a list,
head (unary prefix), which extracts the first element of a non-empty list,
tail (unary prefix), which returns the tail of a non-empty list,
that is to say, the list of all the elements except the first,
length (unary prefix), which returns the length of a list and
!! (binary infix), which extracts an element of a list.
Note that this list indexing operator treats the first element of a list as
occupying position 0.
Some examples of these operators in action should make it clear what they do:
Prelude> 'f':"ear" "fear" Prelude> head [7, 18, 3] 7 Prelude> head "Harvard" 'H' Prelude> tail [7, 18, 3] [18,3] Prelude> tail "Harvard" "arvard" Prelude> length "time" 4 Prelude> length [8, 1, 4, 5, 2] 5 Prelude> "time" !! 2 'm' Prelude> [1, 2, 3, 4] !! 0 1
These operators have the following types:
(:) :: a -> [a] -> [a] head :: [a] -> a tail :: [a] -> [a] length :: [a] -> Int (!!) :: [a] -> Int -> a
(head xs):(tail xs) is the same as
xs is the empty list.
Note also that every list can be represented using the cons operator and the empty list.
[2, 8, 13] can be depicted as
2:8:13:; there's no need to add parentheses as cons associates to the right.
Defining functions that operate on lists
A function to sum the elements of a list of integers can be defined like this:
sum :: Integral a => [a] -> [a] sum ys | ys ==  = 0 | otherwise = head ys + sum (tail ys)
It is better, however, to use pattern-matching thus:
sum :: Integral a => [a] -> [a] sum  = 0 sum (y:ys) = y + sum ys
Here, the patterns are
In dealing with lists a pattern can contain variables and any number of
occurrences of the empty list and the cons operator
List addition and subtraction
Two useful binary infix functions on lists are
++ (list addition)
\\ (list subtraction).
List addition takes two lists as its arguments and sticks them together.
List subtraction removes elements from a list, for example:
[1, 2, 3, 4, 5] \\ [1, 4] is equivalent to
[2, 3, 5],
[1, 1, 1, 1] \\ [1, 4] is equivalent to
[1, 1, 1] and
[1, 1, 1, 1] \\ [1, 1] is equivalent to
List subtraction is not predefined in the version of Haskell used here,
but it can be defined like this:
(\\) :: Eq a => [a] -> [a] -> [a]  \\ _ =  xs \\  = xs (x:xs) \\ (y:ys) | x == y = xs \\ ys | otherwise = (x : (xs \\ [y])) \\ ys
In mathematics the Fibonacci numbers are usually defined like this:
fib 0 = 0 fib 1 = 1 fib i = fib (i - 1) + fib (i - 2)
Although this works in Haskell it is extremely inefficient. A more efficient definition prevents the re-evaluation of the same Fibonacci number. The values are stored in a list. The definition is as follows:
fib j = fiblist !! j fiblist = map f [ 0 .. ] where f 0 = 0 f 1 = 1 f i = fiblist !! (i - 1) + fiblist !! (i - 2)
fiblist contains the infinite list of Fibonacci numbers.
Each element, say the
ith can be expressed in at least two ways,
fib i and as
fiblist !! i.
This version of the Fibonacci numbers is very much more efficient.
© Antoni Diller (30 May 2016)