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 )
= 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) 
= 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 ++ "|  ")