RE: [Axiom-mail] Programming with BTREEs.
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:bill.p...@newsynthesis.org] Sent: Tue 7/04/2009 2:01 PM To: Simon Blomberg Cc: axiom-mail@nongnu.org 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 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
Re: [fricas-devel] Re: [Axiom-mail] Programming with BTREEs.
Dear Ralf, I'm extremely grateful that you answered... Ralf Hemmecke r...@hemmecke.de writes: 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]]] ['a, [1,3], 'b...@bt works for me but [e,[5,1],[[a,[1,1],b],[1,1],[c,[1,2],d...@bt cannot work, I think, because the argument types don't match. You will need to allow also binary trees. Martin ___ Axiom-mail mailing list Axiom-mail@nongnu.org http://lists.nongnu.org/mailman/listinfo/axiom-mail
Re: [fricas-devel] Re: [Axiom-mail] Programming with BTREEs.
but [e,[5,1],[[a,[1,1],b],[1,1],[c,[1,2],d...@bt cannot work, I think, because the argument types don't match. You will need to allow also binary trees. Ooops. You are completely right. The last part in the input file can be replaced by S==Symbol L==List Integer U==Union(BT,S) construct(x: U, l: L, y: U): U == u: BT := if x case S then binaryTree(x::N) else x::BT v: BT := if y case S then binaryTree(y::N) else y::BT binaryTree(u, l, v)::U l: List U := [a,b,c,d,e] (a,b,c,d,e):=(l 1, l 2, l 3, l 4, l 5) u: U := [e,[5,1],[[a,[1,1],b...@u,[1,1],[c,[1,2],d...@u]@U] bt2: BT := u :: BT where the @U part is necessary (though ugly) since otherwise Axiom (oh, FriCAS in my case) falsely creates (25) - [a,[1,2],b] (25) [a,[1,2],b] Type: List(Any) which is a very unspecific (and bad) choice in the pressence of my new function from above and a and b being both variables of type U. Yet another instance of why I hate Any. Ralf ___ Axiom-mail mailing list Axiom-mail@nongnu.org http://lists.nongnu.org/mailman/listinfo/axiom-mail
Re: [fricas-devel] Re: [Axiom-mail] Programming with BTREEs.
Yet another instance of why I hate Any. ... The interpreter seems to like List(Any) more than my specific types. See bolow... :-( Let's do a little programming ... this is the more complicated form. Simon, my example is not completely finished since the MyBinaryTree you find below, doesn't have much functionality (except equality), but it is preferable to BinaryTree, because if you construct a tree in MyBinaryTree(I, L) then you have no chance to construct a tree that has inner nodes that are not of type I and leaves of any other type than L. So the code below is an example of how to translate your tree structure into SPAD code. The input then is B := MyBinaryTree(List Integer, Symbol) t: B := [e,[5,1],[[a,[1,1],b...@b,[1,1],[c,[1,2],d...@b]] The @B is still needed since otherwise the Axiom/FriCAS interpreter tries to construct again something of type List(Any)... Extremely bad behaviour of the interpreter in my eyes... The @B is even needed if you add l: List Symbol := [a,b,c,d,e] (a,b,c,d,e):=(l 1, l 2, l 3, l 4, l 5) before the assignment to t. You have to live with that for the moment, at least you have the chance that adding @B gives a hint to the interpreter of what you actually intended with your input. Try for example t: B := [a,b,c] You get (5) - t:B := [a,b,c] Cannot convert right-hand side of assignment [a,b,c] to an object of the type MyBinaryTree(List(Integer),Symbol) of the left-hand side. Seeing such error message in Axiom is quite common, but wait. Think of it for a moment. You just asked to system to create a tree for you (namely an element t of type B) which would have the inner node b. However, b is of type Symbol and inner nodes should not be of type Symbol, but rather of type List(Integer). So the system is completely right throwing that error message at you. Imagine you are inside a big program and you've put there an assignment like (5). The SPAD compiler will detect that you are doing things where the types do not match and will tell you at compile time (not at runtime). So here is your code... put it into aaa.spad and in Axiom say )co aaa.spad followed by the assignments at the beginning of this mail. Ralf ---rhxBEGIN aaa.spad -- Note that I and L must always be different types. -- MyBinaryTree(Integer, Integer) is forbidden. COUT==CoercibleTo(OutputForm) )abbrev domain MBTREE MyBinaryTree MyBinaryTree(I: COUT, L: COUT): COUT with construct: L - % construct: (L, I, L) - % construct: (%, I, L) - % construct: (L, I, %) - % construct: (%, I, %) - % == add N := Union(I, L) Rep := BinaryTree N construct(l: L): % == binaryTree(l::N)$Rep V == construct construct(l: L, i: I, r: L): % == binaryTree(V l, i, V r) construct(l: %, i: I, r: L): % == binaryTree( l, i, V r) construct(l: L, i: I, r: %): % == binaryTree(V l, i, r) construct(l: %, i: I, r: %): % == binaryTree( l, i, r) coerce(x: %): OutputForm == coerce(x)$Rep ((x: %) = (y: %)): Boolean == (x::Rep) =$Rep (y::Rep) ---rhxEND aaa.spad ___ Axiom-mail mailing list Axiom-mail@nongnu.org http://lists.nongnu.org/mailman/listinfo/axiom-mail
[Axiom-mail] Programming with BTREEs.
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
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 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
