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"}