CSE 150 Lecture Notes - Lecture 40: Natural Number, Concatenation, Merge Sort
Document Summary
A list (over a) is essentially a nite sequence of ele- ments of a. The set, listsa, of lists over a can be de ned recursively: base case: nil listsa, constructor case: if x a and l listsa, then cons(x, a) . , xn] to denote the list cons(x1, cons(x2, . cons(xn, nil) . Basic functions on lists include hd : listsa a, which returns the. Rst element of a (non-empty) list; and tl : listsa listsa, which returns the result of removing the rst element of a (non-empty) list. These are partial functions: if l is a non-empty list, then l = cons(hd(l), tl(l)). The length of a list can be de ned recursively by: (cid:40) length(l) ::= if l = nil. The non-empty lists in x consist of alternating occurrences of 0 and: for example, [1, 0, 1, 0, 1] x.