Reading 16: Recursive Data Types
|Safe from bugs||Easy to understand||Ready for change|
|Correct today and correct in the unknown future.||Communicating clearly with future programmers, including future you.||Designed to accommodate change without rewriting.|
- Understand recursive datatypes
- Read and write datatype definitions
- Understand and implement functions over recursive datatypes
- Understand immutable lists and know the standard operations on immutable lists
- Know and follow a recipe for writing programs with ADTs
Safe from bugs. Recursive datatypes allow us to tackle problems with a recursive or unbounded structure. Implementing appropriate data structures that encapsulate important operations and maintain their own invariants is crucial for correctness.
Ready for change. A recursive ADT, like any ADT, separates abstract values from concrete representations, making it possible to change low-level code and high-level structure of the implementation without changing clients.