CSE 150 Lecture Notes - Lecture 40: Natural Number, Concatenation, Merge Sort

47 views4 pages

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.

Get access

Grade+20% off
$8 USD/m$10 USD/m
Billed $96 USD annually
Grade+
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
40 Verified Answers
Class+
$8 USD/m
Billed $96 USD annually
Class+
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
30 Verified Answers

Related Documents