2
Mar
2009
lists to trees
Gennaro asked me about data structures to contain a tree for his genetic programming in GC (little does he know how clueless I am about data structures), and I recommended a nested list.
It seemed sensible to me, so I set about turning a nested list into a tree diagram, and I have to admit that there were moments that I doubted the plausibility of it, but it turned out OK in the end!
The way to look at it seems to be that you work from the outside in. The outside set of brackets is the root, and then everything inside that is a terminal, with this rule re-applied recursively for each time another list is found.
You can read this diagram either way, as turning a list into a tree, or the other way arround.
Thanks Ben for this,
but this was actually the problem I had,
when you do stucture the list in this way you have noticed that basically there are not “operators” but only “terminals” stored in the list
the operators cannot be stored because are represented by the {} and being the curly brackets stored the terminals, one cannot put also the name of the operators
in simpler word, the Sexpression :
sum(sum(a,b),product(a,b,c))
will end up being:
{{a,b},{a,b,c}}
which means that basically the operators “sum” “product” are not stored and positioned at all!!!! and we do need to store them somehow if afterwards we want to crossover two Sexpression.
either we need an externals list that keeps track of the operator to add to the terminals with a sort of enumeration procedure like:
0000
0000 1000
0100 0101 1100 1101
0200 0201 0210 0211 1200 1201 1210 1211
or maybe to represent the tree with a completely different method such as:
sum(sum(a,b),product(a,b,c))
{{sum,product),{{a,b},{a,b,c}}}
0 1
0 sum a,b
1 product a,b,c
what do you think ?
how would you represent the operators together with the terminals ?
I’m afraid that you are thinking way too hard about this. You are falling into the trap of trying to fix all the problems and catch all the exceptions at a high level.
Operators and operands have essentially equal status in the tree, there is no ‘rule’ about how one can be deployed with respect to another.
This diagram is ripped shamelessly from Pauls forthcoming book.
If you were to spatter some operands and operators arround and then connect them into a tree, then you’d still be able to decompose it into a proper list.
all you need to do is to make sure that there is an option for the operators to take zero opperands.
Then if your tree was:
5(add, 6)
then the result would just be null as you can’t do a ‘5‘ on ‘add‘ and ‘6‘.
but if your graph was
add(5, 6)
then you’d end up with 11 as that is a valid tree.
The evolutionary bit will weed out all the trees that start with non operators pretty quickly.
You may need to do some fiddling about to make it work, but then again, you could just catch the error that tryign to eval(5{Add,6}) will throw and assign null to it.