
  0 | module UnbalancedSet
  1 | 
  2 | import Set
  3 | 
  4 | %default total
  5 | 
  6 | export
  7 | data UnbalancedSet a = E | T (UnbalancedSet a) a (UnbalancedSet a)
  8 | 
  9 | export
 10 | Ord a => Set UnbalancedSet a where
 11 |   empty = E
 12 | 
 13 |   member x E = False
 14 |   member x (T a y b) = assert_total $ case compare x y of
 15 |     LT => member x a
 16 |     GT => member x b
 17 |     EQ => True
 18 | 
 19 |   insert x E = T E x E
 20 |   insert x s@(T a y b) = assert_total $ case compare x y of
 21 |     LT => T (insert x a) y b
 22 |     GT => T a y (insert x b)
 23 |     EQ => s
 24 |