Re: [Axiom-mail] Programming with BTREEs.

[Ralf Hemmecke]

> I sent a message asking for help a couple of weeks ago. Thanks to those 
> who responded. I have a more concrete question:
>
> I am trying to write a simple recursive function to build binary trees 
> from a List object. My test tree is the following:
>
> treeList := [e,[5,1],[[a,[1,1],b], [1,1], [c,[1,2],d]]]

> Each nested level contains a list of three elements, which are to become 
> the left branch, value, and right branch of the tree, respectively. For 
> internal nodes, the value of the tree is a two-element list representing 
> the left- and right branch lengths. The leaves of the tree are to be 
> binary trees with a Symbol as the value (a to e) and empty left - and 
> right branches.

You've already described your tree quite nicely. You have already given 
all the types that are needed. So, in fact, it would be a relatively 
simple task to generate an appropriate tree structure. I said 
'relatively', because it is not totally trivial.

But first my question: do you really want that?
Is it necessary that you put the branch length into the tree?
Why are they there and what are they useful for?
Translating your treeList into a picture gives

      [5,1]
     /     \
    e     [1,1]
         /     \
        /       \
       /         \
    [1,1]       [1,2]
   /     \     /     \
  a       b   c       d

I don't see why there is 5 and 2 in the tree, I cannot connect them to 
lengths.

Next question... Do you really want to convert from these very untyped 
list of list of list .... structures to binary trees? Why don't you 
input your tree correctly in the first place?

My assumption now is that you sit in front of your computer and want to 
construct such a tree structure manually.

OK, let it be that way that you have lists as your internal nodes and 
symbols as your leaves. Let us now (imperfectly) model your data 
structure. (I said "imperfectly", because what follows below allows to 
construct trees whose nodes completely consist of symbols or whose 
leaves are lists of integers of length different from 2. If you really 
want to model your tree with internal leaves being pairs of integers and 
leaves being symbols and no mixtures allowed, you have to invest a bit 
more time and do some programming.)

First, the type of your nodes is (as you would have guessed):

N := Union(Symbol, List Integer)

Then your tree structure is

BT := BinaryTree N

now to make the input a bit shorter, we introduce a shortcut.

B ==> binaryTree  -- the 3-argument version
V ==> binaryTree  -- the 1-argument version

Your original tree would then be...

bt:BT:=B(V e,[5,1],B(B(V a,[1,1],V b),[1,1],B(V c,[1,2],V d)))

... which gives....

   (6)  [e,[5,1],[[a,[1,1],b],[1,1],[c,[1,2],d]]]
                Type: BinaryTree(Union(Symbol,List(Integer)))


Now, of course, you don't want B and V, right? So what now comes is my 
speculation, but I think it should work since an input like

  [a,b,c,d]

ought to be translated into

  construct(a,b,c,d)

but maybe my knowledge of SPAD is too bad...

S==>Symbol
L==>List Integer
construct(x: S, l: L, y: S): BT == binaryTree(V(x::N), l::N, V(y::N))
bt2: BT := [e,[5,1],[[a,[1,1],b],[1,1],[c,[1,2],d]]]

The last line of this run forever on my computer, but that might be 
because I run it with fricas (a fork of the axiom project) with sbcl as 
the underlying lisp.

I hope, I could help you a bit.

My suggestion is: forget about the Any domain. If you encounter it at 
any point in Axiom then that basically says that the interpreter has 
lost track of what you actually mean and you might expect trouble later.

Axiom is unconventional since it works better if you think about 
expected input/output types before you enter anything into the system.

Strong typing is the strength and the weakness of Axiom.

It is good, because, one can handle complex expressions cleanly (for 
example you can distinguish between a polynomial in x with coefficients 
being square matrices of size 3x3 and 3x3 matricies with entries being 
polynomials in x).

It is bad, because it takes quite some time to get used to types and to 
understand the sometimes not so clear error messages. And it is 
frustrating that the system sometimes doesn't let you do things that you 
think would be natural for the expression that you hand to the system.

So I hope you stay with us...
More questions are welcome.

Ralf

PS: Here are the commands written in an input file that you can load 
with ")read aaa.input" from the Axiom command line.

---rhxBEGIN aaa.input
)set messages autoload off
N := Union(Symbol, List Integer)
BT := BinaryTree N
B ==> binaryTree  -- the 3-argument version
V ==> binaryTree  -- the 1-argument version
bt:BT := B(V e,[5,1],B(B(V a,[1,1],V b),[1,1],B(V c,[1,2],V d)))
S==>Symbol
L==>List Integer
construct(x: S, l: L, y: S): BT == binaryTree(V(x::N), l::N, V(y::N))
--bt2: BT := [e,[5,1],[[a,[1,1],b],[1,1],[c,[1,2],d]]]
---rhxEND aaa.input