Re: [Axiom-mail] Programming with BTREEs.

[Bill Page]

Simon,

Here is one solution:

(1) -> )r treelist.input

buildTree(lst:List Any):BTREE(Any) == binaryTree( _
    (car dom(lst.1)='List::SExpression => buildTree(lst.1); _
     binaryTree(lst.1)),_
    lst.2,_
    (car dom(lst.3)='List::SExpression => buildTree(lst.3);_
    binaryTree(lst.3)))

   Function declaration buildTree : List Any -> BinaryTree Any has been
      added to workspace.
                                                    Type: Void

(2) -> treeList := [e,[5,1],[[a,[1,1],b], [1,1], [c,[1,2],d]]]

   (2)  [e,[5,1],[[a,[1,1],b],[1,1],[c,[1,2],d]]]
                                                    Type: List Any

(3) -> buildTree(treeList)

   (3)  [e,[5,1],[[a,[1,1],b],[1,1],[c,[1,2],d]]]
                                                     Type: BinaryTree Any

---

'Any' is a very special type in Axiom. It is probably not a good place
to start to learn about types - or maybe it is if you can tolerate the
complexity of this answer :-)

Explanation:

Overloaded function names are not supported in the Axiom interpreter.
They are only available when writing in the library compiler language
called SPAD. But even if you wrote in SPAD, the function as you wrote
it originally would not work because in SPAD, types are static - that
is they are decided at the time you compile the program, not at the
time you run it. What you wrote requires dynamic type.

The type 'Any' is used to dynamically encapsulate values of any type
as a single type and that way avoid much of the type-checking
mechanism that would otherwise make this sort of routine rather
awkward. It is sometimes referred to in computer science literature as
"duck typing".

There are several ways to query the real type of the value
encapsulated as a value of type Any. This can be done by the function
'dom' which returns something in "Lisp form" called an s-expression.
In the case of a value of type List, the first component of the
s-expression (obtained by the function 'car') is the literal symbol
List.

The way to read the expression:

    (car dom(lst.1)='List::SExpression => buildTree(lst.1); _
     binaryTree(lst.1)),_

is:

   Check if the first item in lst is a List.
   If it is, call 'buildTree' recursively with the value.
   Otherwise call 'binaryTree' with the value.

Ref:

(4) -> )show Any
(4) -> )show SExpression

Regards,
Bill Page.

On Mon, Apr 6, 2009 at 9:55 PM, Simon Blomberg <address@hidden> wrote:
> Hi,
>
> 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. Here is
> my code:
>
> buildTree(lst: List Any):BTREE(Any) == binaryTree(buildTree(lst.1), lst.2,
> buildTree(lst.3))
> buildTree(val:Symbol):BTREE(Any)  == binaryTree(val)
>
> However, calling buildTree(treeList) doesn't work. The second rule
> overwrites the first rule, even though the arguments are of different types.
> I'm still getting my head around how types are specified in Axiom, so any
> assistance would be greatly valued.
>
> Thanks in advance,
>
> Simon.
>
> Simon Blomberg, BSc (Hons), PhD, MAppStat.
> Lecturer and Consultant Statistician
> School of Biological Sciences
> The University of Queensland
> St. Lucia Queensland 4072
> Australia
> T: +61 7 3365 2506
> email: S.Blomberg1_at_uq.edu.au
> http://www.uq.edu.au/~uqsblomb/
>
> Policies:
> 1.  I will NOT analyse your data for you.
> 2.  Your deadline is your problem.
>
> The combination of some data and an aching desire for
> an answer does not ensure that a reasonable answer can
> be extracted from a given body of data. - John Tukey.
>
>
> _______________________________________________
> Axiom-mail mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/axiom-mail
>
>