Lists

Build a list

A list holds values of one type, in order, and any number of them. The literal syntax with commas is sugar for a chain of cons operations:

xs = [1, 2, 3] ys = 1 : 2 : 3 : [] -- xs and ys are the same list

[] is the empty list and also the type constructor, so [Int] is [] Int underneath. The two spellings are interchangeable, and the bracketed one is what people write.

Cons and concatenation

: adds one element to the front in constant time. ++ copies its whole left argument, so the direction of a recursive build decides whether the function is fast or quadratic:

1 : [2,3] -- [1,2,3], cheap [1,2] ++ [3,4] -- [1,2,3,4], copies the left list -- good: build with : countdown 0 = [] countdown n = n : countdown (n - 1)

A list is a linked list, so prepending is free and appending is not. Every list function in the standard library respects that asymmetry.

The basic operations

These cover most traversal and inspection. Note that length walks the whole list, so checking for emptiness with it is a waste:

head [1,2,3] -- 1 tail [1,2,3] -- [2,3] length [1,2,3] -- 3 null [] -- True, constant time reverse [1,2,3] -- [3,2,1] take 2 [1,2,3] -- [1,2] drop 2 [1,2,3] -- [3]

take and drop accept counts larger than the list and return the obvious result instead of failing, which makes them safe in pipelines.

Partial functions

Four names in the list module throw an exception on an empty list: head, tail, last and init. They are convenient in GHCi and dangerous in a service:

-- crashes on [] head [] -- total, always returns a value safeHead :: [a] -> Maybe a safeHead (x:_) = Just x safeHead [] = Nothing

Pattern matching on the two constructors makes the empty case impossible to forget, which is the whole argument of lesson 22.

Next: Ranges and enumeration

Article author: Arthur Isaev