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:
ghci> [1 .. 10] [1,2,3,4,5,6,7,8,9,10] ghci> [3, 5 .. 11] [3,5,7,9,11] ghci> [(-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:
ghci> 'f':"ear" "fear" ghci> head [7, 18, 3] 7 ghci> head "Harvard" 'H' ghci> tail [7, 18, 3] [18,3] ghci> tail "Harvard" "arvard" ghci> length "time" 4 ghci> length [8, 1, 4, 5, 2] 5 ghci> "time" !! 2 'm' ghci> [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
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
sum is actually defined in the Haskell
Prelude; the above definitions are just presented here as examples.
List addition and subtraction
Two useful binary infix functions on lists are
++ (list addition)
\\ (list subtraction).
In talking about the operator
various idioms are used.
People talk about joining two lists together or concatenating them.
++ itself is often called append.
These days, list subtraction is more usually called list difference.
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 difference is not included in the standard Prelude.
If you want to use it,
you need to include the library of functions
which you do as follows:
ghci> import Data.List ghci> [1,8,77,11] \\  [1,8,11]
You can also add
to any file you load into GHCi.
In mathematics the Fibonacci numbers are usually defined like this:
fib :: Integer -> Integer 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 :: Integer -> Integer 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
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 (17 September 2021)