RichardO'Keefe@sri-unix.UUCP (04/12/84)
From: Richard O'Keefe (on ERCC DEC-10)
Purpose: Flatten various binary trees to lists and convert back.
This file was originally for PRESS, where you often want to take
a tree such as 1+x+0+(u*v+9)+(x^2+2) and flatten it to a list
such as [1,x,u*v,9,x^2,2] so that you can easily pick out all the
constants or all the terms involving x or something, without having
to write N different sets of predicates to handle N different
binary operators. It can be useful for other things as well.
The <operator>_to_list predicates take a binary tree (where leaf
nodes are anything not labelled by the operator) and flatten it
to a list. They also omit "units" of that operator, that is, if
the operator is & {| + *} the constant true {false 0 1} will not
appear in the list. The predicate
binary_to_list(Tree, Operator, Unit, Before, After)
enables you to make your own versions. Note that the answer is
accumulated in the differnce Before-After.
binary_to_list(Tree, Operator, Before, After)
lets you convert trees where the operator has no unit.
The well known and not often useful predicate "flatten" is a not
very interesting special case of binary_to_list/5.
The list_to_<operator> predicates take a list and turn it back
into a tree. Now there is an interesting question here: is
[a,b,c] to be turned into f(a,f(b,c)) or into f(f(a,b),c)? The
former is a good idea for & | and '.', while the latter is a
good idea for + and *. My solution was to have the top-level
predicate check whether the Operator is a yfx operator (such as
+ and * are) and if so to generate f(f(a,b),c). In all other
cases (xfy,xfx, or no operator declaration) f(a,f(b,c)) is
generated.
list_to_binary(List, Operator, Unit, Tree)
lets you make your own versions. If the list is [] the Unit will
be returned, that is the only use of the Unit.
list_to_binary(List, Operator, Tree)
should be used when the Operator has no Unit, if given an empty
list it will fail.
[ FLAT.PL is available from the {SU-SCORE} <Prolog> directory.
if you cannot get it for yourself, drop me a note. -ed]