module S04 (
  -- * Exercise 2
  {-| Using the definitions

   @
   foldr f b []     = b
   foldr f b (x:xs) = x `f` foldr f b xs
   @

   and

   @
   foldl f b []     = b
   foldl f b (x:xs) = foldl f (b `f` x) xs
   @

   The expression @foldr (-) 0 [1,2,3]@ can be evaluated as
   
   @
   foldr (-) 0 [1,2,3]
     = 1 - foldr (-) 0 [2,3]
     = 1 - (2 - foldr (-) 0 [3])
     = 1 - (2 - (3 - foldr (-) 0 []))
     = 1 - (2 - (3 - 0))
     = 2
   @

   and the expression @foldl (-) 0 [1,2,3]@ as

   @
   foldl (-) 0 [1,2,3]
     = foldl (-) (0 - 1) [2,3]
     = foldl (-) ((0 - 1) - 2) [3]
     = foldl (-) (((0 - 1) - 2) - 3) []
     = ((0 - 1) - 2) - 3
     = - 6
   @
   -}

  -- * Exercise 3
  isSorted,

  -- * Exercises 4 and 5
  -- |See "Grep".

  -- * Exercise 6
  showBTree
  ) where
import BTree

isSorted :: Ord a => BTree a -> Bool
isSorted = isSortedList . flatten
  where isSortedList []     = True
        isSortedList (x:xs) = all (x<=) xs && isSortedList xs

showBTree :: Show a => BTree a -> String
showBTree t = show' t []
  where
    show' t prefix = case t of
        Empty -> prefix' ++ ".\n"
        Node x l r -> elt x ++ right r ++ left l
      where
        prefix' =
          if null prefix then []
          else take (length prefix - 3) prefix ++ "+- "
        elt   x = prefix' ++ show x ++ "\n"
        left  l = show' l (prefix ++ "   ")
        right r = show' r (prefix ++ "|  ")