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 lists without duplicates
  
  module SetAsOrderedList
    ( Set, empty, singleton, set, union, element, equal ) where
  
    import Data.List(nub, sort)
  
    type Set = [Int]
  
    invariant :: Set -> Bool
    invariant ns = and [ m < n | (m,n) <- zip ns (tail ns) ]
  
    empty :: Set
    empty = []
  
    singleton :: Int -> Set
    singleton n = [n]
  
    set :: [Int] -> Set
    set ns = nub (sort ns)
  
    union :: Set -> Set -> Set
    ms `union` []                     = ms
    [] `union` ns                     = ns
    (m:ms) `union` (n:ns) | m == n    = m : (ms `union` ns)
                          | m < n     = m : (ms `union` (n:ns))
                          | otherwise = n : ((m:ms) `union` ns)
  
    element :: Int -> Set -> Bool
    m `element` []               = False
    m `element` (n:ns) | m < n   = False
                       | m == n  = True
                       | m > n   = m `element` ns
  
    equal :: Set -> Set -> Bool
    ms `equal` ns = ms == ns
  
  