Thu Feb 5 17:29:21 CET 2009


For a simple static C program with a bit of dynamic data, this is a
simple list structure based only on concatenation, with "next"
pointers embedded in the objects.

This works for pure trees (flat trees).

Conceptually, only these operations are necessary:
     * a PUSH operation of a singleton to a stack.
     * a REVERSE operation to finalize construction preserving order
     * a FOR operation for traversal

If objects have built-in list pointers, there is conceptually no
"element".  All things are lists, and the primitive operations are
"overlay_1" and "split_1".

overlay_1 (abcd... , 1234...) = a1234...
split_1   (abcd...)           = bcd...

I'm not sure if this way of looking at it is so useful, but there _is_
a difference between objects that contain a next pointer, and obects
that are contained in a separate container structure (i.e. cons
cells).  Using embedded next is commonplace, and is easier to use with
manual memory management, so maybe it's better to stick to it.

Another way of looking at it: if datastructure construction is not
time-critical, using quadratic list insertion is not really a
problem..  That way append and iteration might be enough.

The problem with embedded "next" pointers is that if you want to put
the objects in an alternative container, you get two different
containement mechanism (one built-in, one explicit).