Puzzle part 5: What data structure do we need?

In order to try to solve this problem elegantly, or at least concisely, I imagined what kind of data structure I would really like to have available. What I came up with was something like Lisp lists.

Lisp is one of the oldest programming languages, and its fundamental data structure is based on five operations. If s is one of these data structures (Lispers call them S-expressions), then:

empty(s) is true if s is empty and false otherwise.

If s is not empty, car(s) is the first element of s.

If s is not empty, cdr(s) is a list that contains all but the first element of s.

If x is an element and s is a list, then cons(x, s) is a list such that car(cons(x, s)) is x and cdr(cons(x, s)) is s

nil is a list with no elements.

How might such a data structure look in C++?

Suppose that T is a type that can stand as an element of a vector. Then I imagined a template type Seq<T> such that if we defined

Seq<T> s;

then

s.empty() is true if s has no elements and false otherwise.

s.head() is the first element of s, provided that s is not empty.

s.tail() is a Seq containing all but the first element of s, provided that s is not empty.

cons(x, s) is a Seq that contains x followed by the elements of s.

Finally, Seq<T>() is an empty list.

With that data structure available, the problem becomes a good deal easier to solve.

Posted by Andrew Koenig at 11:59 AM  Permalink