||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|| Misc. user-defined types

|| Enumeration type
weekday ::= Mon | Tue | Wed | Thu | Fri
weekend ::= Sat | Sun

|| A union
day  ::= InWeek weekday | NonWeek weekend

|| Two structured types
numlist  ::= NullNumNode | NumNode num numlist
list *   ::= NullNode | Node (*) (list *)

|| Binary expression tree
exptree ::= Nil | ExpLeaf num | ExpNode char exptree exptree

|| A function to evaluate the tree.
evalexp Nil = error "eval on nil tree."
evalexp (ExpLeaf num) = num
evalexp (ExpNode '+' left right) = (evalexp left) + (evalexp right)

||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|| Heap abstract type

abstype
  heap *
with
  emptyheap :: heap *
  isempty   :: heap * -> bool
  additem   :: * -> heap * -> heap *
  getmin    :: heap * -> *
  popmin    :: heap * -> heap *

heapnode * ::= Nil | HeapNode * (heapnode *) (heapnode *)

heap * == heapnode *

emptyheap = Nil

isempty Nil              = True
isempty (HeapNode a b c) = False

|| additem is a severely broken implementation; we really need to
|| randomize adds to the left/right subtrees but that adds complexity
|| and doesn't teach you that much more about types so I left it like
|| this
additem item Nil = (HeapNode item Nil Nil)
additem item (HeapNode a b c)
        = (HeapNode (a) (additem item b) (c)) , if a < item
        = (HeapNode (item) (b) (additem a c)) , otherwise

getmin Nil = error "getmin of empty heap" 
getmin (HeapNode a b c) = a

popmin Nil = error "popmin of empty heap"
popmin (HeapNode a b c)
    = Nil                               , if b = Nil & c = Nil
    = (HeapNode (getmin b) (popmin b) c), if c = Nil
    = (HeapNode (getmin c) b (popmin c)), if b = Nil
    = (HeapNode (getmin b) (popmin b) c), if (getmin b) <= (getmin c)
    = (HeapNode (getmin c) b (popmin c)), otherwise

|| And a convenience function, for easy testing
addlist []    h = h
addlist (a:x) h = additem a (addlist x h)

