@
chrisname
Remember, though, that the compiler cannot resolve an arbitrarily infinite data structure. That's why you cannot nest structures of the same type:
1 2 3 4
|
struct A
{
A a; // compile error -- "incomplete/unresolved type" or "infinite recursion" or somesuch
};
|
Rather, you need to use
pointers:
1 2 3 4
|
struct A
{
A* a; // fine
};
|
The same holds true for tuple lists, or more specifically,
s-expressions. Each element can be either an atom (not a pair) or another pair.
1 2 3 4 5 6 7 8 9 10
|
struct pair
{
bool is_pair; // Is our car an atom or a pair?
union
{
const char* a; // In this example, our atoms are simple strings
pair* p;
} car; // Traditional name for the first element in a pair
pair* cdr; // Traditional name for the second element in a pair
};
|
This structure has several characteristics, which can be summarized thus:
null or
empty
Represented by a pair { false, NULL, NULL }
Written as
()
atom (in this example, a
string)
Represented by a pair { false, string, NULL }
Written as
abc
, etc.
(Notice that we never use just a plain
const char* -- it must always be wrapped up in a "pair" struct.)
pair
Represented by a pair { false, string, pair } or pair { true, pair, pair }
Written as
(abc . cdr)
or
(abc . cdr)
This last one needs some thought -- a
pair is a
string or a
pair which has been paired with another
pair (which may be either an atom or a pair).
Some convenient constructors help:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
|
pair* new_empty()
{
pair* e = new pair;
e.is_pair = false;
e.car.s = NULL;
e.cdr = NULL;
return e;
}
pair* new_atom( const char* s )
{
pair* a = new pair;
a.is_pair = false;
a.car.s = s;
a.cdr = NULL;
return a;
}
pair* new_atom( pair* p )
{
pair* a = new pair;
a.is_pair = true;
a.car.p = p;
a.cdr = NULL;
return a;
}
pair* new_pair( const char* s, pair* p )
{
pair* a = new_atom( s );
a.cdr = p;
return a;
}
pair* new_pair( pair* p1, pair* p2 )
{
pair* a = new_atom( p1 );
a.cdr = p2;
return a;
}
|
You can now represent any arbitrary nested pairs. For example, a
proper list is a bunch of nested pairs that terminate with a null (an empty pair). That could be written as:
(one . (two . (three . ())))
but it is often shortened to just:
(one two three)
1 2
|
// list <-- (one two three)
pair* list = new_pair( "one", new_pair( "two", new_pair( "three", new_empty() ) ) );
|
Without the final null, we would have an
improper list, and write it as:
(one two . three)
1 2
|
// list <-- (one two . three)
pair* list = new_pair( "one", new_pair( "two", new_atom( "three" ) ) );
|
If you want to play around with this kind of stuff, be sure to watch for memory leaks!
:-)