List #

Recursive form #

Lists in Haskell are recursive.

Definition (finite list in Haskell).

• [] is the empty list,
• if x is an element and xs a list, then x : xs is a list.

In addition, all elements in a list must have the same type. If this type is a, then the list has type [a].

Example. The Haskell list

$\qquad$5 : (2 : [])

stands for the mathematical list

$\qquad5,2$

[Int] is a valid type for this list (as well as [Integer],[Float], etc.), because Int is a valid type for 5 and 2.

Warning. The empty list [] has type [a] for any type a.

Examples. The following types are valid for the empty list:

• [String] (list of strings)
• [Int] (list of bounded integers)
• [[Int]] (list of lists of bounded integers)
• etc.

Terminology. The operator : is pronounced “cons”.
Intuitively, it adds an element to the beginning of a list.

Syntax. The operator : associates to the right. This makes some parentheses redundant.

Examples.

list	in Haskell	omitting parentheses
$5, 2$	5 : (2 : [])	5 : 2 : []
$3, 5, 2$	3 : (5 : (2 : []))	3 : 5 : 2 : []

Terminology. If x : xs is a list, then:

• x is called its head,
• xs is called its tail.

The head is intuitively the first element of the list, and the tail is the rest of it.

Note. If the list x : xs has type [a], then

• x has type a, and
• xs has type [a].

Syntax. As syntactic sugar, a list can also be written in non-recursive form, within square brackets.

Examples.

Haskell list	brackets notation
2 : []	[2]
5 : 2 : []	[5,2]
3 : 5 : 2 : []	[3,5,2]

Concatenation #

Syntax. The operator ++ concatenates two lists (with the same type).

Examples.

expression	evaluation
[2,1] ++ [3,2,5]	[2,1,3,2,5]
[2,1] ++ []	[2,1]
[] ++ [3,2,5]	[3,2,5]

Exercise

Complete the following table

expression	is syntactically valid	possible type (if valid)
1 : 2	no
1 : 2 : []	yes	[Int]
1 : [2]
[1] : [2]
[1] : [[2]]
[1] : [[2,3]]
[1,2] : [[3]]
[[1],[2]] : [[3]]
[1] ++ [2,3]
[1] ++ [[2],[3]]
[[1]] ++ [[2],[3]]

Solution

expression	is syntactically valid	possible type (if valid)
1 : 2 : []	yes	[Int]
1 : 2	no
1 : [2]	yes	[Int]
[1] : [2]	no
[1] : [[2]]	yes	[[Int]]
[1] : [[2],[3]]	yes	[[Int]]
[1,2] : [[3]]	yes	[[Int]]
[[1],[2]] : [[3]]	no
[1] ++ [2,3]	yes	[Int]
[1] ++ [[2],[3]]	no
[[1]] ++ [[2],[3]]	yes	[[Int]]

List patterns #

Base pattern. [] is a pattern. It matches the empty list.

Composite patterns. If p and q are patterns, then

$\qquad$ (p : q)

is also a pattern. It matches a list if:

• p matches its head, and
• q matches its tail.

Syntactic sugar.

• [p] is equivalent to (p : [])
• [p,q] is equivalent to (p : q : [])
• etc.

Example. The following function discards the first element of a list, unless the list has length $\le 1$.

discardHead :: [Int] -> [Int]
discardHead [] = []         -- empty list
discardHead [x] = [x]       -- singleton list
discardHead (_ : xs) = xs   -- otherwise

startsWithTwins :: [(String,String)] -> Bool
startsWithTwins [] = False
startsWithTwins ((x,y) : _) = x == y

String #

A string in Haskell is a list of characters.
Precisely, the type String is an alias for the type [Char].

Example. The following function returns True iff the input string starts with an uppercase ASCII letter:

startsWithUp :: String -> Bool
startsWithUp [] = False                      -- empty string
startsWithUp (c : _) = 'A' <= c && c <= 'Z'  -- here `<=` is the alphabetical order