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"
Type: Union(String,...)
(4) -> search(2, t)
(4) "b"
Type: Union(String,...)
(5) -> search(3, t)
(5) "failed"
Type: Union("failed",...)
--
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.
)abbrev domain STREE STree
OF ==> OutputForm
--data STree key value =
-- Empty | Node key value (STree key value) (STree key value)
-- deriving (Show)
-- key, value are type parameters (parameters of a domain in Spad).
-- It is either Empty or a node containing key, value, left subtree,
-- right subtree.
-- `deriving (Show)' means the default definition for printing of this
-- data to String.
STree(Key: OrderedSet, Value: CoercibleTo OF): CoercibleTo OF with
-- search :: Ord key => key -> STree key value -> Maybe value
-- `::' is `:' of Spad, `=' is `==', `:=' of Spad.
-- `Ord key =>' corresponds to the condition of
-- key : OrderedSet in the domain declaration in Spad.
-- The used `compare' operation is of the class Show.
-- `search' is a polymorphic function. And in Spad, it needs, probably,
-- to be exported by the domain STree.
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]
coerce(t: %): OF ==
rep(t) case "empty" => "()"::OF
n: Node := (rep t)::Node
hconcat ["(k="::OF, n.key::OF,", v="::OF, n.value::OF,
", l="::OF, n.left::OF, ", r="::OF, n.right::OF, ")"::OF]
-- 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
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)
