✳flâneur — a map of the web's best reading

Reading 11: Recursive Data Types

web.mit.edu · 8,257 words · saved by 1 readers

In this reading we’ll look at recursively-defined types, how to specify operations on such types, and how to implement them. Our main example will be immutable lists. Before we introduce recursive data types — which have a recursive structure of both data and computation — take a minute to review what you know about recursive functions. You should have already practiced this heavily in 6.101 (formerly called 6.009). Here are some 6.101 readings to review: If you are at all uncertain about what these terms mean and how to use them, take some time to review this 6.101 material before going on. Just as a recursive function is defined in terms of itself, a recursive data type is defined in terms of itself. We’ll see the same need for base and recursive cases, which will now appear as different variants of the abstract type. Some of our recursive types will be list-like and some will be tree-like. Consider this recursive implementation of the factorial function. For factorial(3), how many t

Reading 11: Recursive Data Types Reading 11: Recursive Data Types Software in 6.102 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. Objectives Understand recursive data types Read and write data type definitions Understand and implement functions over recursive data types Understand immutable lists and know the standard operations on immutable lists Know and follow a recipe for writing programs with ADTs Introduction In this

Explore this link on the map →

saved by

related reading