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 20 : Data Representation
  
  -- Representing sets as ordered lists without duplicates
  
  module Chap20_data_representation_sets_as_lists_without_duplicates 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)
  
  s0 = set [1,42,2,7,1,3,2]
  
  s1 = set [3,1,2] `union` set [1,7,4,1]
  
  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
  
  