Top down vs bottom up recursive data definition?

Question

While reading "Essentials of Programming Languages" I came across top down and bottom up definitions for list of integers.While I understand what these definitions say. But I am not able to understand fine details of top down vs. bottom up approach. How do I look at a definition and say weather it is top down or bottom up?

top-down A Scheme list is a list of integers if and only if either

1. it is the empty list, or

2. it is a pair whose car is an integer and whose cdr is a list of integers.

bottom-up The set List-of-Int is the smallest set of Scheme lists satisfying the following two properties:

1. () ∈ List-of-Int, and

2. if n ∈ Int and l ∈ List-of-Int, then (n . l) ∈ List-of-Int.

Answer 1

These two concepts are related to the notion of induction and recursion. Both of these concepts are ways of describing infinitely large families of objects, though they differ in their approach.

When you're defining something bottom-up, you are defining it inductively. The idea is that you start out with a set of fixed elements and a way of combining those elements into new elements. In the bottom-up definition above, initially the only element in the set of all list of integers is the empty list. You also have a rule which allows you to take a list in the set of lists of integers and grow it into something one step larger by prepending an integer.

When you're defining something top-down, you are defining it recursively. The idea is that you're beginning with some very large family of objects - in this case, every possible list - and then describing just those lists that are composed solely of integers. Usually elements defined coinductively are defined by taking existing objects and ruling out objects that don't match. For example, in the example of lists of integers, you define whether something is a list of integers by taking any list that you feel like and then verifying that if you keep breaking it down and down and down you eventually bottom out at some objects that you know are lists of integers (in this case, just the empty list).

The two forms are actually equivalent to one another, but they serve different purposes. Induction tries to build up the entire set of valid objects, then defines all objects matching the description. Recursion doesn't initially define anything, but then checks whether any object you have matches some criteria by piecing it apart and verifying it. Due to the magical way in which the two are mathematically defined, any inductive definition can be turned into a recursive definition and vice-versa (assuming that all objects you're talking about are finite).

EDIT: If you're really up for a fun ride, you might want to check out the related concepts of coinduction and corecursion. These are a mathematical dual to induction and recursion and provide an entirely different way of thinking about how to define a data structure. In particular, they allow for infinitely large data structures, which can't normally be defined inductively. Interestingly, there's a connection between coinduction, corecursion, induction, and recursion in terms of fixed points. You can think of the inductive definition of a data structure as the smallest set meeting some property, while the coinductive definition is the largest set with that property. It's really cool!