15 List Syntax and Semantics.

Pronunciation

• [] is pronounced "nil"
• :: is pronounced "cons," short for "constructor" (these are borrowed from Lisp)

Syntax

• [] is the empty list
• e1 :: e2 prepends element e1 to list e2
• [e1; e2] is syntactic sugar for e1 :: e2 :: []

Semantics

• [] is a value
• To evaluate e1 :: e2
  • evaluate e1 to value v1
  • evaluate e2 to a (list) value v2
  • return v1 :: v2

List types

For any type t, the type t list describes list where all elements have type t.

• [1; 2; 3] : int list
• [true] : bool list
• [[1 + 1; 2 - 3]; [3 * 7]] : int list list

[] : 'a if e1 : t and e2 : t list, then e1 :: e2 : t list.