More Self-referential Data Definitions

Lists and natural numbers are two classes of data whose description requires self-referential data definitions. Both data definitions consist of two clauses; both have a single self-reference. Many interesting classes of data, however, require more complex definitions than that. Indeed, there is no end to the variations. It is therefore necessary to learn how to formulate data definitions on our own, starting with informal descriptions of information. Once we have those, we can just follow a slightly modified design recipe for self-referential data definitions.

• Structures in Structures
• Extended Exercise: Binary Search Trees
• Lists in Lists
• Extended Exercise: Evaluating Scheme