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

module Chap20_data_representation_sets_as_ordered_trees where

data Set = Nil | Node Set Int Set
  deriving Show

s0 =
  Node (Node (Node (Node Nil 1 Nil) 2 Nil)
             6
             (Node Nil 10 (Node Nil 12 Nil)))
       17
       (Node (Node (Node Nil 18 Nil)
                   20
                   (Node Nil 29 (Node Nil 34 Nil)))
             35
             (Node (Node Nil 37 Nil)
                   42
                   (Node (Node Nil 48 Nil) 50 Nil)))

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

singleton :: Int -> Set
singleton n = Node Nil n Nil

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)

s1 = insert 11 s0

set :: [Int] -> Set
set = foldr insert empty

union :: Set -> Set -> Set
ms `union` ns = foldr insert ms (list ns)

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

b1 = 15 `element` s1

equal :: Set -> Set -> Bool
s `equal` t = list s == list t