Solutions to Chapter 3 (p. 70), questions 6-8

#6. Here is the documentation for sortBy. The signature says it all:

sortBy :: (a -> a -> Ordering) -> [a] -> [a]

The first argument is a comparison function. Recall compare, which was briefly presented in Chapter 2 (p. 22-23). What we have to do is provide sortBy with a function that compares list lengths, so:

sortByLength :: [[a]] -> [[a]]
sortByLength list = sortBy compareLength list
             where compareLength l1 l2 = compare (length l1) (length l2)

Note that if you're including this in a .hs file to be loaded by ghci, you need to add import Data.List as the first line of that file.

#7. We need a special pattern to handle the single-element-list case, since the separator should not follow the last element:

intersperse :: a -> [[a]] -> [a]
intersperse _ [] = []
intersperse _ [x] = x
intersperse sep (x:xs) = x ++ [sep] ++ intersperse sep xs

Since for either the empty list or the one-element list, we don't care about the separator's value, a wildcard (_) is used.

#8. (At least in my copy of the book, this mistakenly appears as question 9 -- they've numbered a paragraph in question 7 as item #8.) We use this definition of Tree:

data Tree a = Node a (Tree a) (Tree a)
            | Empty
              deriving (Show)

The solution is:

treeHeight :: Tree a -> Int
treeHeight Empty = 0
treeHeight (Node _ t1 t2) = 1 + max (treeHeight t1) (treeHeight t2)

The function max wasn't mentioned, but it's not really a surprise, right? Anyway, as always with functional languages, where recursion is so natural, algorithms like DFS seem trivial.