module S06 (
  -- * Exercises 2 to 4
  -- | See <../solutions/s06.pdf>.

  -- * Exercise 5
  safeTail, safeInit, safeLast,
  -- * Exercise 6
  equals
  ) where
import BTree (BTree(..))
import qualified BTree

applyIfNotNull :: ([a] -> b) -> [a] -> Maybe b
applyIfNotNull _ [] = Nothing
applyIfNotNull f xs = Just (f xs)

safeTail :: [a] -> Maybe [a]
safeTail = applyIfNotNull tail

safeInit :: [a] -> Maybe [a]
safeInit = applyIfNotNull init

safeLast :: [a] -> Maybe a
safeLast = applyIfNotNull last

newtype Set a = Set (BTree a)

isSubset :: Ord a => Set a -> Set a -> Bool
isSubset (Set t) (Set u) = t `isSubtree` u
  where isSubtree Empty _       = True
        isSubtree (Node x l r) t =
          x `memTree` t && l `isSubtree` t && r `isSubtree` t

equals :: Ord a => Set a -> Set a -> Bool
equals s t = s `isSubset` t && t `isSubset` s

mem :: Ord a => a -> Set a -> Bool
mem x (Set t) = x `memTree` t

memTree x Empty = False
memTree x (Node y l r) =
  case compare x y of
    EQ -> True
    LT -> x `memTree` l
    GT -> x `memTree` r