Construction and Implementation

List Constructors

List have two constructors: [] and :

[] :: [a]

(:) :: a -> [a] -> [a]

The notation

[15, 12, 21]

Is a shortcut for

15 : 12 : 21 : []

Which means

15 : (12 : (21 : []))

Lists in Haskell are simply linked lists. Constructors [] and : work in constant time (DS sharing)

l1 = 3 : 2 : 1 : []
l2 = 4 : l1

Operator ++ returns the concatenation of two lists (time proportional to the length of the first list).


let xs = ["apple", "banana"]
let ys = "cherry" : xs     -- prepend
let zs = xs ++ ["cherry"]  -- append

Because lists are also immutable in Haskell, you have to create a new list if you want to prepend / append elements to an existing one.