RE: [Axiom-mail] Programming with BTREEs.

[Simon Blomberg]

Hi Bill,

Thanks for that! I really needed to know about dom. Many years ago, I used XLisp-Stat as my primary programming platform, so I am used to car, cdr and friends. I have a question. In your code there is the clause:

car dom(lst.1)='List::SExpression

When and how does this get evaluated? When I type it in to the interpreter, I get:

(21) -> car dom(treeList.1) = 'List::SExpression

   (21)  Variable= List

Which does not get evaluated to a Boolean False. What gives? I think I understand the rest of your code. Thanks again.

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.



-----Original Message-----
From: Bill Page [mailto:address@hidden]
Sent: Tue 7/04/2009 2:01 PM
To: Simon Blomberg
Cc: address@hidden
Subject: Re: [Axiom-mail] Programming with BTREEs.

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
>
>