On Sun, Mar 04, 2012 at 07:00:38PM +0100, Ralf Hemmecke wrote:
>> I try to follow this, only to have a simpler example.
>> Define a
>> binary tree with INT in its nodes:
>
> That perhaps...
>
> https://svn.origo.ethz.ch/algebraist/trunk/aldor/lib/axllib/test/tree.as
>
> Well, you'd have to remove semicola and braces, of course and add the
> )abbrev line, but it looks pretty much like what you want.
>
> A leaf ther is something of the form [nodevalue, [], []], i.e. a value
> together with two empty (binary) trees.
tree.as : I fear dealing with Aldor + Spad will be even more difficult.
for me.
But here what seems now to work:
-- Binary tree over Integer -------------------------------------------
OF ==> OutputForm
INT ==> Integer
Node ==> Record(val : INT, left : %, right : %)
)abbrev domain BTREE BTree
BTree() : Export == Implementation where
Export == SetCategory with
coerce : % -> OF
empty : () -> %
tree : (INT, %, %) -> %
tree1 : INT -> %
sumTree : % -> INT
Implementation == add
Rep := Union(empty : "empty", node : Node)
coerce(t) : OutputForm ==
t case empty => "empty" :: OF
nd := t.node
l := coerce nd.left
r := coerce nd.right
hconcat["(", nd.val :: OF, ", ", l, ", ", r, ")"]
empty() == ["empty"]
tree(n, l, r) == [[n, l, r]]
sumTree tr ==
tr case empty => 0
tr case node =>
nd := tr.node
nd.val + sumTree(nd.left) + sumTree(nd.right)
tree1(n) == -- make example tree
tree( n, tree(n+1, empty(), empty()),
tree(n-1, empty(), empty()) )
-----------------------------------------------------------------------
1. I wonder why ["empty"] is needed instead of "empty"
(I mimiked this stupidly fron src/algebra/tree.spad*).
Similarly is tree(n, l, r) == [[n, l, r]],
-- as if additional [] coerces it to Rep.
2. Initially there was no "coerce(t) == "
The interpreter reported that coerce is missed from BTree.
What kind of coerce ?
Finally I guessed that it computes tree1(1), but cannot output.
So, probably, coerce(t) : OutputForm == ... is needed.
3. A recursive Record + Union cannot at all express the needed
recursive Tree type.
To define this recursive type it is needed
`domain' + Record + Union, and to use % inside Record !
And all this -- for expressing of what is expressed in a single line
in Haskell.
All right, at least it works!
Thank you for help,
------
Sergei
[email protected]
--
You received this message because you are subscribed to the Google Groups
"FriCAS - computer algebra system" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/fricas-devel?hl=en.
