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 s.blombe...@uq.edu.au 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
Axiom-mail@nongnu.org
http://lists.nongnu.org/mailman/listinfo/axiom-mail
___
Axiom-mail mailing list
Axiom-mail@nongnu.org
http://lists.nongnu.org/mailman/listinfo/axiom-mail
