)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)