Haskell, in common with many other functional languages, provide list types as a fundamental data structuring mechanism.

Definition

In Haskell, a list type for any given base type may be easily constructed by naming the base type.

<list-type> ::="[" <type> "]"

• [Int] : lists of Ints.
• [Polygon] : lists of Polygons.
• [Char] : Haskell's String data type is a lists of Chars.
• [(Int, Float)] : lists of Int \(\times\) Float tuples.

Construction

List values can be easily constructed by explicit enumeration of values. For example, a list of 4 [Char] \(\times\) Int 2-tuples:

[("black", 0), ("brown" 1), ("red", 2), ("orange", 3)]

Construction may also use the : operator to "cons" an element to the front of a given list, or the ++ operator to append to lists together.

("black", 0):[("brown" 1), ("red", 2), ("orange", 3)]
("black", 0):("brown" 1):[("red", 2), ("orange", 3)]
("black", 0):("brown" 1):("red", 2),[("orange", 3)]
("black", 0):("brown" 1):("red", 2): ("orange", 3):[]
[("black", 0), ("brown" 1)] ++ [("red", 2), ("orange", 3)]

These examples all construct the same list value.

Access

Haskell list elements can be accessed by pattern-matching or by explicit recognition and access functions: null, head, tail.

• Pattern matching

totalof3[x, y, z]  = x + y + z

total [] = 0
total (a:as) = a + total as

• Access functions

total xs 
  | null xs = 0
  | otherwise = head xs + total(tail xs)

• null is a boolean function returning true if its argument is an empty list, false otherwise.
• head returns the first element of a nonempty list
• tail returns the sublist remaining after removing the first element of a list.

List Processing in Haskell

• Functional List Processing
• Recursive List Processing