Lists: cons, append and the total helpers
The cons chain
A list is not an array and not a special syntax: it is a data type with two constructors, the empty list [] and the cons cell :, which holds one element and the rest of the list. Every list you write is sugar over that chain:
[1, 2, 3]
1 : 2 : 3 : []
The two lines above are the same value. The second one is what the compiler sees, and it is also how a list is taken apart: a pattern (x : xs) names the first element and the rest. A cons cell is cheap, because it does not copy the tail: it points at it. That is why prepending is constant time while appending is not, and the next two sections show both in a real program.
The type is written [a], or [] a in the older spelling you still see in type signatures: a list of Int is [Int], a list of strings is [String], and a string is itself [Char], which is why "abc" and ['a', 'b', 'c'] are the same value.
A list in a program
One program, nine lines of output, one operation per line. The annotations such as (1 :: Int) and ([] :: [Int]) are there because -Wall warns when a numeric type or an empty list has no other constraint: the lesson on numbers explains defaulting.
module Main (main) where
main :: IO ()
main = do
print ((1 :: Int) : [2, 3])
print ([1, 2] ++ [3, 4] :: [Int])
print (length ["a", "b", "c"])
print (null ([] :: [Int]))
print (reverse [1, 2, 3] :: [Int])
print (head [1, 2, 3] :: Int)
print (tail [1, 2, 3] :: [Int])
print (last [1, 2, 3] :: Int)
print (init [1, 2, 3] :: [Int])
ghc -Wall -O1 -o listops listops.hs
./listops
[1,2,3]
[1,2,3,4]
3
True
[3,2,1]
1
[2,3]
3
[1,2]
The build prints two warnings, and they are part of the lesson rather than a defect of the page: see the next section. The output is what the nine expressions evaluate to. Note the shape of print of a list: it shows the elements with commas and no spaces, exactly as show would print them, so [1,2,3] and not [1, 2, 3].
head and tail are partial
Four of those functions are total: length, null and reverse work for every list, empty included, and so does ++. head, tail, last and init are partial: they have no answer for [], and they throw at run time. GHC 9.10 says so during the build, which is why the program above is not warning-free:
listops.hs:10:12: warning: [GHC-63394] [-Wx-partial]
In the use of 'head'
(imported from Prelude, but defined in GHC.Internal.List):
"This is a partial function, it throws an error on empty lists. Use pattern matching, 'Data.List.uncons' or 'Data.Maybe.listToMaybe' instead. Consider refactoring to use "Data.List.NonEmpty"."
|
10 | print (head [1, 2, 3] :: Int)
| ^^^^
The same warning is printed a second time for tail, with a message that suggests drop 1. The compiler is telling you something a type cannot: the function is defined for every list by its signature and fails for one of them. Two ways out, both shown later in the course:
- Pattern match on the list yourself, in the lesson on pattern matching: headOr fallback (x : _) = x.
- Use a function whose type admits the empty case: Data.Maybe.listToMaybe :: [a] -> Maybe a for the first element, or drop 1 for the tail, which answers [].
GHC 9.8 added this warning and GHC 9.10 has it in -Wall. An older compiler builds the same program silently; a newer one nudges you towards total code, and the course follows that advice in the programs it writes by hand.
Append is not free
++ joins two lists, and it does it by walking the whole left argument: every cons cell of the left list is copied into a new one that points at the right list. The right argument is not touched at all. That asymmetry is the whole cost model:
module Main (main) where
main :: IO ()
main = do
print ([1, 2] ++ [3, 4] :: [Int])
print (1 : 2 : 3 : 4 : [] :: [Int])
print ("ab" ++ "cd" :: String)
print (length ([1, 2] ++ [3, 4] :: [Int]))
print (["a"] ++ ["b"] ++ ["c"] :: [String])
ghc -Wall -O1 -o append append.hs
./append
[1,2,3,4]
[1,2,3,4]
"abcd"
4
["a","b","c"]
The first two lines are the same value again: prepending four elements and appending an empty list have the same result and different costs. The last line is written ["a"] ++ ["b"] ++ ["c"], and ++ is infixr 5, so it groups as ["a"] ++ (["b"] ++ ["c"]): the single-element lists are copied, which is nothing here and everything in a loop that appends one element at a time.
That is the trap the next lessons keep coming back to. A function that builds a list with xs ++ [x] at every step walks the growing list every time and costs the square of its length, while x : xs costs one cell. The lesson on recursion shows the slow reverse written with ++ and the fast one written with :.
The total helpers
The Prelude has a small toolbox for lists, and it is worth knowing which functions answer for every list. The ones used above:
- length :: [a] -> Int walks the list and counts the cells, so it is linear, not constant.
- null :: [a] -> Bool answers whether the list is empty without walking it, which is why null xs is better than length xs == 0 in a guard.
- reverse :: [a] -> [a] is linear: it walks the list once and builds the result with cons cells.
- take, drop, elem, ++ and : are total as well; they answer for the empty list and for a count larger than the list.
And the partial ones in the same family, head, tail, last, init, maximum, minimum and foldr1, all of which throw on the empty list. When a function of yours needs one of them, a pattern match and an explicit empty case make the same program total with a few more lines.
Exercises
- Write [4, 5] in cons form, then check your answer by printing both in one program.
- Print length ("abc" ++ "de") and explain why the answer is five and not six.
- Replace length xs == 0 with null xs in a guard of your own and say what the program saves.
- Build the list [1,2,3] by appending three one-element lists, then build the same list with :, and count the cons cells each version copies.
- Compile a program that calls head on a list and read the GHC-63394 warning. Rewrite the call as a pattern match with a fallback value.
- Use init and last on a list of three elements and predict the two lines before you run the program.
Questions
A new set of questions in a new order every time. Choose one answer for each, then check.
-
Which expression is the same value as
[1, 2, 3]?Answer
1 : 2 : 3 : []A list is the empty list or a cons cell holding one element and the rest, so the three elements are three cons cells ending in [].
-
What does
length ["a", "b", "c"]return?Answer
3
length counts the cells of the list, not the characters of its strings, and prints as the number 3.
-
What does this program print?
module Main (main) where main :: IO () main = print (null ([] :: [Int]))Answer
True
null answers whether a list is empty, and the empty list is empty, so it prints True.
-
What happens when
head ([] :: [Int])is evaluated?Answer
It throws an error at run time
head has no answer for the empty list: the type promises an Int and there is none, so the program dies when the expression is forced.
-
What does
[1, 2] ++ [3]evaluate to?Answer
[1,2,3]
Append joins two lists of the same element type in order: the cells of the left list, then the right list.
-
Which operation is constant time, whatever the length of the list?
Answer
Prepending with
:A cons cell points at the existing tail, so prepending allocates one cell. Append, reverse and length all walk the list.
-
What does
reverse [1, 2, 3]return?Answer
[3,2,1]
reverse walks the list once and builds the result with cons cells, so the order of the elements is inverted.
-
What does this program print?
module Main (main) where main :: IO () main = print (tail [1] :: [Int], init [1] :: [Int])Answer
([],[])
A one-element list has an empty tail and an empty init, so both lines print the empty list.
-
Why does
-Wallwarn aboutheadin GHC 9.10?Answer
head is partial: it throws on the empty list
The warning GHC-63394 names the partial functions of the Prelude, and head cannot answer for [], so a total rewrite is suggested.
-
A function appends one element with
xs ++ [x]at every recursive step. What is the cost for a list of length n?Answer
It walks the growing list each time, about n squared cells in total
Append copies every cell of its left argument, and the left argument grows by one at each step, so the total work is the sum 1 + 2 + ... + n.
The code on this page was built with GHC 9.10.3 and run on Alpine Linux 3.24.3 (x86_64) in a Docker container.
Article author: Arthur Isaev