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

   @
   foldr k z xs = go xs
     where go []     = z
           go (y:ys) = y `k` go ys
   @

   and

   @
   foldl f z xs = lgo z xs
     where lgo z []     = z
           lgo z (x:xs) = lgo (f z x) xs
   @

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

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

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

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

  -- * Exercise 3
  isSorted,
  -- * 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' Empty        _      = ""
        show' (Node x l r) prefix = elt ++ right ++ mid ++ left
          where prefix' = if null prefix
                  then []
                  else take (length prefix - 3) prefix ++ "+- "
                elt     = prefix' ++ show x ++ "\n"
                left    = show' l (prefix ++ "   ")
                right   = show' r (prefix ++ "|  ")
                mid     = case l of { Empty -> ""; _ -> prefix ++ "|  \n"}