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:

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:

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

  1. Write [4, 5] in cons form, then check your answer by printing both in one program.
  2. Print length ("abc" ++ "de") and explain why the answer is five and not six.
  3. Replace length xs == 0 with null xs in a guard of your own and say what the program saves.
  4. 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.
  5. 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.
  6. 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.

  1. 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 [].

  2. 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.

  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.

  4. 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.

  5. 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.

  6. 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.

  7. 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.

  8. 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.

  9. Why does -Wall warn about head in 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.

  10. 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