COM1340 - Winter 2003
Recursive types
January 8, 2003

Informally, a ``recursive type'' means a data structure that may have a piece that has the same type as the whole structure. In C or C++, for example, you can declare structures that have pieces like the whole: 
  struct mytree {
    int x;
    struct mytree *left;
    struct mytree *right;
  };

In this type, why are the self-similar pieces pointers to structures, rather than structures, here? What sizes of trees can we denote using this type?

This C/C++ structure might have arisen from a slightly more mathematical definition:

A mytree is either

Note the recursion in the definition -- that recursion corresponds directly to the recursion in the struct type above. In this definition, why do we need the first alternative?

An extremely useful recursive type is the list. Just as lists are useful in everyday life (shopping lists, phone lists, to-do lists), they're handy in programs. Lucky for us, the list is a native data structure in Scheme.

Let's define the type of data in Scheme, which includes lists.

A Scheme value is either

Atoms are constants, such as numbers, strings, and symbols: 
 42
 3.14159
 "the quick brown fox"
 'truth-and-beauty
 'a

[Go to first, previous, next page]

Last modified: Mon, Jan 6, 2003, 4:50 pm US/Eastern
HTML conversion by TeX2page 4p4k3