Solutions to Chapter 4 (p. 97)

This exercises section has numerous mistakes and typos in it, including incorrect numbering (at least, that's the print I have). The numbers I'm using here are the "right" ones, not the ones that appear in print.

#1. It's foldl, of course, because in each step we have to multiply everything we've seen so far by 10 -- and "everything we've seen so far" refers to stuff on the left of the currently-added digit.

Because the minus sign can only appear as the first character, we'll use a special pattern just for it, before folding.

import Data.Char

asInt_fold :: String -> Int
asInt_fold ('-':xs) = -(asInt_fold xs)
asInt_fold xs = foldl step 0 xs
                where step x y = 10 * x + (digitToInt y)

#2. I can only assume the authors meant "" and "-" to be reported as errors. I also assume they wish us to use error directly, rather than rely on digitToInt doing the work for us. Finally, I assume we can't use isDigit, which wasn't introduced yet.

asInt_fold :: String -> Int
asInt_fold [] = error "Contains no digits"
asInt_fold ('-':xs) = -(asInt_fold xs)
asInt_fold xs = foldl step 0 xs
   where step x y | (y >= '0') && (y <= '9') = 10 * x + (digitToInt y)
                  | otherwise = error ("Not a digit '" ++ [y] ++ "'")

#3. (sigh) The signature of asInt_either is broken in the text. It should be:

type ErrorMessage = String
asInt_either :: String -> Either ErrorMessage Int

And of course, Either wasn't presented yet...! To add insult to injury, the book's index doesn't have the correct pointer to information about Either: you can read about it in page 210 (Chapter 8); or you can use the GHC online docs. To keep things simple, I will not be using the either function, just the Either type, with patterns and case to tell Left from Right:

type ErrorMessage = String

asInt_either :: String -> Either ErrorMessage Int
asInt_either [] = Left "Contains no digits"
asInt_either ('-':xs) = case inner of
                          Left err  -> Left err
                          Right val -> Right (-val)
   where inner = (asInt_either xs)
asInt_either xs = foldl step (Right 0) xs
   where step (Right x) y | (y >= '0') && (y <= '9') = Right (10 * x + (digitToInt y))
                          | otherwise = Left ("Not a digit '" ++ [y] ++ "'")
         step (Left err) _ = Left err

What makes the code so unattractive is the fact we have to deconstruct the answer at every folding step, and reconstruct it right back. If it was deconstructed to a Left, it stays a Left with the same error message; if it was deconstructed to a Right, we proceed normally in the step, but must wrap the result in a Right constructor again.

#4. Simply append the nested lists to each other:

myConcat :: [[a]] -> [a]
myConcat xs = foldr (++) [] xs

#5. Recursive:

takeWhile_rec :: (a -> Bool) -> [a] -> [a]
takeWhile_rec _ [] = []
takeWhile_rec pred (x:xs) | pred x    = x : takeWhile_rec pred xs
                          | otherwise = []

takeWhile is very similar to filter, except that if the predicate isn't met, we don't proceed (return an empty list instead of the accumulator):

takeWhile_foldr :: (a -> Bool) -> [a] -> [a]
takeWhile_foldr pred xs = foldr stepr [] xs
  where stepr x acc | pred x = x : acc
                    | otherwise = []

#6. What does groupBy do? The first argument is of type a -> a -> Bool, meaning it's a relation on the type a (for example, ">" is a relation on the integers; == is a relation on any comparable type; etc.) This, plus the function name, gives us a pretty strong hint. Let's check it out, in ghci:

Prelude> :module Data.List
Prelude Data.List> groupBy (>) [1,2,3,4,5,6,7]
[[1],[2],[3],[4],[5],[6],[7]]
Prelude Data.List> groupBy (>) [4,3,2,1]
[[4,3,2,1]]
Prelude Data.List> groupBy (>) [4,3,4,2,1]
[[4,3],[4,2,1]]
Prelude Data.List> groupBy (==) [4,3,4,2,1]
[[4],[3],[4],[2],[1]]
Prelude Data.List> groupBy (==) [1,1,1,2,1,1,2,2,2,1,2]
[[1,1,1],[2],[1,1],[2,2,2],[1],[2]]

Seems like it compares pairs of elements, and as long as each element fulfills the relation with the previous one, they are added to the same group. But then, something funny happens when you try other stuff:

*Main Data.List> groupBy (>) [4,2,3,1,3,5,2,3,2,1]
[[4,2,3,1,3],[5,2,3,2,1]]

Huh?

Well, apparently groupBy picks the first elements, and groups to it all elements that are in the relation with it; once an element not in the relationship with the first one is found, it is used to start a new group, and further elements will be compared to this head of the new group. And so on. So, again, each element is compared not with the preceding element, but with the first element (the head) of the group being constructed.

This only goes to show how important it is to use varied input sets when testing your code.

Now, let's see how this can be implemented using fold. Because each element is compared not to its direct neighbor, but to the first of its group, foldr makes little sense: seeing the rightmost element, we don't know what to compare it with! So, with foldl:

groupBy_foldl :: (a -> a -> Bool) -> [a] -> [[a]]
groupBy_foldl p xs = foldl step [] xs
  where step [] x = [[x]]
        step acc x | p (head (last acc)) x = (init acc) ++ [((last acc) ++ [x])]
                   | otherwise             = acc ++ [[x]]

Here, the accumulator (acc) is a list of lists, and to get the first element of the last list we use head (last acc). I assume last isn't a very efficient function, so it might be more efficient to keep the last element of acc on its own, and append it to acc only when moving to a new sublist (or when we're done). This yields the less-readable function:

groupBy_foldl2 :: (a -> a -> Bool) -> [a] -> [[a]]
groupBy_foldl2 p xs = acc ++ [lastAcc]
  where (acc, lastAcc) = foldl step ([], []) xs
        step (acc, []) x = (acc, [x])
        step (acc, lastAcc) x | p (head lastAcc) x = (acc, lastAcc ++ [x])
                              | otherwise          = (acc ++ [lastAcc], [x])

... But while it's less readable, I'm not at all certain it's also faster. Besides, using fold is not the fastest way to implement groupBy anyway. My advice, as always, is to leave optimizations out of the game until you're certain that there actually is a performance problem.

#7. For any, we can use either left or right folding; here's a naive attempt:

any_foldl p xs = foldl step False xs
  where step acc x = acc || (p x)

any_foldr p xs = foldr step False xs
  where step x acc = acc || (p x)

Note that we are applying the predicate p to each x, and or-ing the results. So why not apply p using map?

any_foldl p xs = foldl (||) False (map p xs)

any_foldr p xs = foldr (||) False (map p xs)

Remember that Haskell is lazy, so this does not imply that we first apply p to all xs; rather, it is applied on a per-need basis. And indeed, this version is both shorter, easier to understand, and faster. And finally, the foldr version is far superior to the foldl one. To see why, ask yourself which of them allows Haskell to use short-circuit evaluation for the "or" operator.

For cycle... wait, cycle wasn't introduced yet. And it involves infinite lists, a concept which wasn't introduced yet, either. So we'll skip it for now.

For words, left and right versions both use an accumulator that includes the words collected so far, plus a boolean indicating if we're currently handling whitespace:

import Data.Char
 -- (for isSpace)

words_foldl :: String -> [String]
words_foldl ln = fst(foldl step ([],True) ln)
  where step (acc, True) x | isSpace x = (acc, True)
                           | otherwise = (acc ++ [[x]], False)
        step (acc, False) x | isSpace x = (acc, True)
                            | otherwise = ((init acc) ++ [(last acc) ++ [x]], False)

words_foldr :: String -> [String]
words_foldr ln = fst(foldr step ([],True) ln)
  where step x (acc, True) | isSpace x = (acc, True)
                           | otherwise = ([x] : acc, False)
        step x (acc, False) | isSpace x = (acc, True)
                            | otherwise = ((x : (head acc)) : tail acc, False)

Again, the right-folding version is better, this time since head and tail are preferred over init and last.

Finally, for unlines:

unlines_foldl :: [String] -> String
unlines_foldl lns = foldl step [] lns
  where step acc ln = acc ++ ln ++ "\n"

unlines_foldr :: [String] -> String
unlines_foldr lns = foldr step [] lns
  where step ln acc = ln ++ "\n" ++ acc

Solutions to Chapter 4 (p. 84)

#1.

safeHead :: [a] -> Maybe a
safeHead [] = Nothing
safeHead (x:xs) = Just x

safeTail :: [a] -> Maybe [a]
safeTail [] = Nothing
safeTail (x:xs) = Just xs

safeLast :: [a] -> Maybe a
safeLast [] = Nothing
safeLast [x] = Just x
safeLast (x:xs) = safeLast xs

safeInit :: [a] -> Maybe [a]
safeInit [] = Nothing
safeInit [x] = Just []
safeInit (x:xs) = Just (x:fromMaybe xs (safeInit xs))

You need to import Data.Maybe for the last one. It is also possible to implement safeLast using last, like this:

safeLast :: [a] -> Maybe a
safeLast [] = Nothing
safeLast xs = Just last xs

But in fact, this is true for every one of those functions: if the input is empty, return Nothing; otherwise, reutrn Just whatever-the-unsafe-variant-returns. So a quick solution to all four would be:

safeVariantOf :: ([a] -> b) -> ([a] -> Maybe b)
safeVariantOf _ [] = Nothing
safeVariantOf func xs = Just (func xs)

safeHead :: [a] -> Maybe a
safeHead = safeVariantOf head

safeTail :: [a] -> [a]
safeTail = safeVariantOf tail

safeLast :: [a] -> Maybe a
safeLast = safeVariantOf last

safeInit :: [a] -> [a]
safeInit = safeVariantOf init

Note how the type of safeVariantOf does not assume any relationship between the original function's input type ([a]) and output type (b). That's because b is sometimes [a] and sometimes just a. In fact, this block of code is one of those cases where the code looks simpler and easier to understand without the type declarations:

safeVariantOf _ [] = Nothing
safeVariantOf func xs = Just (func xs)

safeHead = safeVariantOf head
safeTail = safeVariantOf tail
safeLast = safeVariantOf last
safeInit = safeVariantOf init

Finally, while the authors suggest using Maybe, another approach on safe variants is providing a default when no data is available. This works very naturally with the list-returning functions, where the obvious default is an empty list:

tailOrEmpty :: [a] -> [a]
tailOrEmpty [] = []
tailOrEmpty (x:xs) = xs

initOrEmpty :: [a] -> [a]
initOrEmpty [] = []
initOrEmpty [x] = []
initOrEmpty (x:xs) = x:initOrEmpty xs

For head and last, the user has to provide the default as an extra argument:

headOrDefault :: [a] -> a -> a
headOrDefault [] a = a
headOrDefault (x:xs) _ = x

lastOrDefault :: [a] -> a -> a
lastOrDefault [] x = x
lastOrDefault [x] _ = x
lastOrDefault (x:xs) _ = lastOrDefault xs x

#2. Confusingly, the function parameter should return False for characters that are not boundaries; e.g., to implement words, we'll need a predicate that returns False for whitespace (only).

splitWith :: (a -> Bool) -> [a] -> [[a]]
splitWith _ [] = []
splitWith pred (x:xs) | not (pred x) = splitWith pred xs
splitWith pred xs = (takeWhile pred xs):(splitWith pred next)
                    where rest = dropWhile pred xs
                          rev pred x = not (pred x)
                          next = dropWhile (rev pred) rest

We use takeWhile and dropWhile because a sequence of spaces shouldn't result in multiple empty words (between each pair of spaces). It is also important to correctly handle any leading or trailing spaces.

Using function composition (the dot operator) will make this simpler, since rev will not be required; but it wasn't introduced yet in the book.

#3. Set myFuction to firstWords, defined thus:

firstWords :: String -> String
firstWords input = unlines (firstWordsList (lines input))
    where firstWordsList :: [String] -> [String]
          firstWordsList [] = []
          firstWordsList (ln:lns) = headOrDefault (words ln) "" : 
                                    firstWordsList lns

Note that to extract the first word from a line, we can't simply use head (words ln), since the line could be empty. We use headOrDefault, defined in question #1 above.

(To be continued...)

#4. What a beautiful example of lacking specifications... How should the function behave if there are more than two lines (abort? ignore the extra line? transpose them all?). How should it handle cases there some lines are shorter than others? For this solution, I assume a transposition of all lines, as wide as the shortest line in the input.

We should obviously first split the input into a list of lines (strings), process this list, and then re-wrap the list of lines as one long string. So,

transpose :: String -> String
transpose [] = []
transpose inp = unlines (transposeLines (lines inp))

But how do you define transposeLines? The type is obviously a list of strings to a list of strings ([String] -> [String]). For the n^th line, we have to zip each character in that line with the output of processing all the following lines (remember that the pattern format x:xs makes us handle the list from the end backwards, assuming we recurse for xs). So, zipping should be done using a function that takes one character (from the n^th line) and one line (one item from the transpose result of all lines following the current one), and prepend the character to that line. So we get:

transposeLines :: [String] -> [String]
transposeLines [ln] = ??? -- not handled yet
transposeLines (ln:lns) = zipWith prepend ln (transposeLines lns)

prepend :: Char -> String -> String
prepend ch str = [ch] ++ str

For the single-line (bottom of the recursion) case, we need to take a line and give a list of lines, each containing a single character from the original line. In other words, we break up the line:

transposeLines :: [String] -> [String]
transposeLines [ln] = breakup ln
transposeLines (ln:lns) = zipWith prepend ln (transposeLines lns)

breakUp :: String -> [String]
breakUp [] = []
breakUp (ch:chs) = [[ch]] ++ breakUp chs

In fact, using breakUp, we can simplify the handling of the n^th line as well, by breaking up each line as it is processed, and zipping with standard concatanation. This implies we don't need prepend, and the final result is:

transpose :: String -> String
transpose [] = []
transpose inp = unlines (transposeLines (lines inp))
   where transposeLines :: [String] -> [String]
         transposeLines [ln] = breakUp ln
         transposeLines (ln:lns) = zipWith (++) (breakUp ln) (transposeLines lns)
         breakUp :: String -> [String]
         breakUp [] = []
         breakUp (ch:chs) = [[ch]] ++ breakUp chs

Solutions to Chapter 3 (p. 70), questions 9-12

(The misnumbering in my printed copy continues, and these wrongly appear as questions 10-13.)

#9. Trivially,

data Direction = LeftTurn | RightTurn | Straight
                 deriving (Show)

I'd use Left and Right, except that there already are constructors of these names defined in Prelude, and the book hasn't yet discussed how to deal with such conflicts.

#10. If the question seems unclear, think of it this way: you're driving from point p1 to point p2; it's a straight line. Now, you have to reach point p3. Do you drive straight on, make a left turn, or make a right turn?

At first it seems this requires lots of trigonometrics to solve, but in fact, there's a simple formula that yields the required result, based on the sign (negative, positive, or zero) of the two vectors defined by the two path segments (p1 to p2 and p2 to p3):

data Point = Point { x :: Double, y :: Double }
             deriving (Show)

turn :: Point -> Point -> Point -> Direction
turn p1 p2 p3 | prod > 0  = LeftTurn
              | prod < 0  = RightTurn
              | otherwise = Straight
     where prod = ((x(p2) - x(p1)) * (y(p3) - y(p1))) - 
                  ((y(p2) - y(p1)) * (x(p3) - x(p1)))

#11. The trick is to define a pattern that extracts the three leading elements of the list. And remember, when progressing to the next step, that you keep two out of these three (rather than considereding all three as "processed").

directions :: [Point] -> [Direction]
directions ps | length ps < 3 = []
directions (p1:p2:p3:ps) = turn p1 p2 p3 : directions (p2:p3:ps)

#12. This is where I draw the line (no pun intended) -- this is too much math before breakfast for me. I might come back to this question later.

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.

Solutions to Chapter 3 (p. 69), questions 1-5

#1. I prefer starting with the simple case (here, an empty list) and moving up to the more complex cases. So:

myLength :: [a] -> Int
myLength [] = 0
myLength (_:xs) = 1 + myLength xs

Because have patterns for both possible list constructors, we can be assured that our pattern covers all possible lists.

#2. The signature appears as the first line above. I never write a function without writing its signature first, and I recommend this to you, too.

#3. The mean of a list is the sum of its elements, divided by its length. There actually is a sum function in Prelude, but let's assume there isn't, and define our own, calling it total:

total :: [Double] -> Double
total [] = 0.0
total (x:xs) = x + total xs

mean :: [Double] -> Double
mean xs = (total xs) / fromIntegral (length xs)

But why not make total a local function?

mean :: [Double] -> Double
mean xs = (total xs) / fromIntegral (length xs)
          where total :: [Double] -> Double
                total [] = 0.0
                total (x:xs) = x + total xs

Both length and total iterate over the list; so we have two iterations, which can be wasteful. Can we optimize this by computing both the sum and the length in parallel, using a single iteration? Here goes:

mean :: [Double] -> Double
mean xs = let (len, sum) = lengthAndSum xs
          in sum / fromIntegral len
          where lenAndSum :: [Double] -> (Int, Double)
                lenAndSum [] = (0, 0.0)
                lenAndSum (x:xs) = (1+fst(lenAndSum xs), x+snd(lenAndsum xs))

It's certainly less readable. But... is it faster? In non-methodic testing I did with GHC 6.10.2, the answer is a resounding no: the "optimized" version is actually noticeably slower. (You can test it on lists such as [0, 0.01 .. 1000].) The main lesson is that in Haskell, in most cases, you should write straightforward, readable code, and let the compiler handle the optimizations. (This is true in most programming languages, in fact, especially when only learning the language. We all know the old maxims about premature optimizations.)

You might suspect that the performance hit comes from invoking lenAndSum twice at each recursive iteration, but this isn't the case; Haskell easily optimizes this part away (it's easy to write a single-invocation version and verify that).

BTW, when using the simple

mean xs = (sum xs) / fromIntegral (length xs)

the results are far faster than either approach outlined above. It's not that the built-in sum has some dark magic or hard-coded optimizations: it's just implemented differently than our taken on it (total). You can find the source code here, and it looks like this:

sum     l       = sum' l 0
  where
    sum' []     a = a
    sum' (x:xs) a = sum' xs (a+x)

It doesn't use anything that wasn't presented so far. This specific style of using recursion is discussed in detail in Chapter 4 of the book.

#4. Using ++ for list-concatanation, we get:

pali :: [a] -> [a]
pali [] = []
pali (x:xs) = [x] ++ pali xs ++ [x]

#5. Let's start by thinking about the signature of isPali. At first, it looks like what we need is:

isPali :: [a] -> Bool

so that it works with any list (just like pali works with any type). However, once we begin implementing it we realize that we must be able to compare list members (e.g., the first element must equal the last). And we can't use comparisons if we know nothing about the type! (The equality relation is not defined for all data types.)

Later on, we shall see how to overcome this by limiting the type parameter to "comparable types". For now, let us limit the solution to lists of Char (so we could test it on strings):

isPali :: [Char] -> Bool
isPali xs = (xs == reverse xs)

The reverse function is part of the Prelude (and it's very easy to define by yourself, anyway).

Note the format used for computing a boolean value: I've seen too many expressions like if pred true else false, especially in procedural languages (e.g., if (pred) return true; else return false;). This is very sad -- you can just use the predicate value directly, e.g., return pred;. I've used the same approach in the definition of isPali above.

BTW, the book's definition of a palindrome seems to require it to be of even length. It's easy to "upgrade" the function to meet this requirement, like this:

isPali :: [Char] -> Bool
isPali xs = (xs == reverse xs) && (even (length xs))

Solutions to Chapter 3 (p. 60)

#1. Given the List definition:

data List a = Cons a (List a)
            | Nil
              deriving (Show)

We can define toList thus:

toList (Cons a as) = a : toList as
toList Nil = []

Each line replaces the List constructor with the matching [a] constructor: Cost is replaced by :, whereas Nil is replaced by an empty list. Because the built-in list type [a] is defined using recursion, so is this conversion process.

#2.

data Tree a = Node a (Maybe (Tree a)) (Maybe (Tree a))
              deriving (Show)

Solutions to Chapter 2 (p. 39)

For the excercise on page 25, just type each line into ghci.

Page 39:

#1. The function can only select an element from the list: there's no other way it can obtain a value of type a; in particular, it cannot create new values of this "unknown" type.

Thus, possible valid behaviors include returning the first element, returning the second element, etc.; returning the last element, returning the last-but-one element, etc.; returning the middle element; and so on.

Interestingly, a function with this signature in Haskell cannot return a "random" element from the list, because (for functions with no IO) the same value must be returned every time the function is called with the same input.

#2. Using if:

lastButOne :: [a] -> a
lastButOne (x:xs) = if length xs == 1
                    then x
                    else lastButOne xs

With pattern matching (introduced in the following chapter), this can be simplified as:

lastButOne :: [a] -> a
lastButOne (x1:[x2]) = x1
lastButOne (x:xs) = lastButOne xs

#3. For either version, trying this on a too-short list (e.g., lastButOne "no") results in the error message "Non-exhaustive patterns in function".

Solutions to Chapter 1 (p. 16)

Excercises 1 and 2 are mere ghci interaction assignments.

#3. The original WC program counts lines, and looks like this (p.15):

main = interact wordCount
       where wordCount input = show (length (lines input)) ++ "\n"

The key part is length (lines input)), which applies the length function to the result of lines input. The excercise tells us about the words function, which makes the solution trivial:

main = interact wordCount
       where wordCount input = show (length (words input)) ++ "\n"

#4. For the number of characters, we just need the length of the original input string, thus:

main = interact wordCount
       where wordCount input = show (length input) ++ "\n"

Welcome!

In this blog, I will post solutions to the exercises from Real World Haskell, the excellent book by Bryan O'Sullivan, John Goerzen, and Don Stewart (O'Reilly, 2008).

Each solution will only use technologies and concepts presented up to that point in the book. (Some excercises become trivial using stuff that wasn't taught yet, but that's missing the point.)

Solutions will be accompanied by explanations (where relevant). And of course, this being a blog, everybody is invited to join the discussion.