content: -- D. Sannella. M Fourman, H. Peng and P. Wadler
  -- Introduction to Computation: Haskell, Logic and Automata
  -- Undergraduate Topics in Computer Science, Springer (2021)
  -- ISBN 978-3-030-76907
  
  -- Chapter 21 : Data Abstraction
  
  -- Sets as ordered trees as an abstract data type, with expanded API
  
  module AbstractSetAsOrderedTree
    ( Set, empty, isEmpty, singleton, select, set, union, delete, element, equal ) where
  
    data Set = Nil | Node Set Int Set
  
    invariant :: Set -> Bool
    invariant Nil          = True
    invariant (Node l n r) =
      and [ m < n | m <- list l ] &&
      and [ m > n | m <- list r ] &&
      invariant l && invariant r
  
    list :: Set -> [Int]
    list Nil          = []
    list (Node l n r) = list l ++ [n] ++ list r
  
    empty :: Set
    empty = Nil
  
    isEmpty :: Set -> Bool
    isEmpty Nil          = True
    isEmpty (Node _ _ _) = False
  
    singleton :: Int -> Set
    singleton n = Node Nil n Nil
  
    select :: Set -> Int
    select s = head (list s)
  
    insert :: Int -> Set -> Set
    insert m Nil = Node Nil m Nil
    insert m (Node l n r)
      | m == n   = Node l n r
      | m < n    = Node (insert m l) n r
      | m > n    = Node l n (insert m r)
  
    set :: [Int] -> Set
    set = foldr insert empty
  
    union :: Set -> Set -> Set
    ms `union` ns = foldr insert ms (list ns)
  
    delete :: Int -> Set -> Set
    delete m Nil           = Nil
    delete m (Node l n r)
      | m < n               = Node (delete m l) n r
      | m > n               = Node l n (delete m r)
      | m == n && isEmpty l = r
      | m == n && isEmpty r = l
      | otherwise           = Node l min (delete min r)
                                where min = select r
  
    element :: Int -> Set -> Bool
    m `element` Nil = False
    m `element` (Node l n r)
      | m == n      = True
      | m < n       = m `element` l
      | m > n       = m `element` r
  
    equal :: Set -> Set -> Bool
    s `equal` t = list s == list t
  