On Thu, May 03, 2012 at 12:32:50PM +0200, Ralf Hemmecke wrote:
> Of course, this STree type is wrong in the sense that it allows the
> creation of trees that are not appropriate for binary search. (Node 3
> below lives in the wrong branch.) Nevertheless, it's an easy exercise.
>
> Ralf
>
> (1) -> T := STree(Integer, String)
>
> (1) STree(Integer,String)
>
> Type: Type
> (2) -> t: T := node(1,"a", empty(), node(2, "b", node(3, "c", empty(),
> empty()), empty()))
>
> (2) (k=1, v="a", l=(), r=(k=2, v="b", l=(k=3, v="c", l=(), r=()),
> r=()))
> Type: STree(Integer,String)
> (3) -> search(1, t)
>
> (3) "a"
> []
So, the Haskell code is
------------------------------------------------------------------------
data STree key value =
Empty | Node key value (STree key value) (STree key value)
deriving (Show)
search :: Ord key => key -> STree key value -> Maybe value
search k tab = case tab of
Empty -> Nothing
Node k' v leftBranch rightBranch ->
case compare k k'
of
EQ -> Just v
LT -> search k leftBranch
_ -> search k rightBranch
------------------------------------------------------------------------
and the Spad code is
------------------------------------------------------------------------
)abbrev domain STREE STree
OF ==> OutputForm
STree(Key: OrderedSet, Value: CoercibleTo OF): CoercibleTo OF with
search: (Key, %) -> Union("failed", Value)
empty: () -> %
node: (Key, Value, %, %) -> %
== add
Node == Record(key: Key, value: Value, left: %, right: %)
Rep == Union("empty", Node)
rep(x:%):Rep == x pretend Rep
per(x:Rep):% == x pretend %
empty(): % == per "empty"
node(k: Key, v: Value, l: %, r: %): % == per [k, v, l, r]
search(k: Key, t: %): Union("failed", Value) ==
rep(t) case "empty" => "failed"
n: Node := (rep t)::Node
n.key = k => n.value
n.key > k => search(k, n.left)
search(k, n.right)
-----------------------------------------------------------------------
I remove the implementation for `coerce' because a similar implementation
for `show' must be added to the Haskell program -- if we skip
`deriving (Show)'.
Thank you for a useful sample of programming.
I am sorry: it is not "considerably more complex",
it is _a bit more complex_.
As to my subjective opinion, it is considerably more complex, because it
is difficult for me to guess of adding
`node: ...', `Node == Record ...', `rep' and `per'.
But with CostructedDomain, it was more difficult
(I could show the code).
The necessity of type recursion is joint there with a particular
_tagged union_ to express the domain construction.
Regards,
------
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.
