University of Oxford Logo University of OxfordDepartment of Computer Science - Home
On Facebook
Facebook
Follow us on twitter
Twitter
Linked in
Linked in
Flickr
Flickr
Google plus
Google plus
Digg
Digg
Pinterest
Pinterest
Stumble Upon
Stumble Upon

Thinking Functionally with Haskell: Errata (as of 5th October 2018)

If you have any more corrections, please send them to tfwh@cs.ox.ac.uk!

Page 6, line -6:

Missing colon: the function showRun should yield a string of the form "be: 2\n".

Thanks to Nobuo Yamashita for spotting this.

Page 11:

In the definition of convert3 the guard in the second clause should be t==0, not n==0.

Thanks to Kevin Boulain for spotting this.

Page 19, Answer to Exercise F:

The argument type of showEntry should be (Label,[Word]), not [(Label,[Word])].

Thanks to Daniel Alonso and Zachariah Levine for spotting this.

Page 20:

The URL for the paper History of Haskell has changed; perhaps the DOI 10.1145/1238844.1238856 is a more robust reference.

Thanks to David Johnson-Davies for spotting this.

Page 25, lines 8-9:

"Operator names consist only of symbols."

Thanks to Nobuo Yamashita for spotting this.

Page 25, line 10:

For consistency with p9, "back quotes" should be "back-quotes".

Thanks to Gilbert Bonthonnou for spotting this.

Page 33, line 2 and line -6:

Missing close quote: the string should be

"Hello" ++ "\n" ++ ...

Thanks to Nobuo Yamashita and Gebrezgi Bocretsion for spotting this.

Page 36:

The three occurrences of sqrt d should be sqrt disc.

Thanks to Zachariah Levine for spotting this.

Page 38, line 8:

The function toUpper is not exported from the prelude, so the question should be about "the name of the standard function".

Thanks to Nobuo Yamashita for spotting this.

Page 43, line 4:

The type of (-) is Num a => a -> a -> a.

Thanks to Nobuo Yamashita for spotting this.

Page 45, Answer to Exercise E:

The last part of Exercise E says "Finally, count the number of functions with type Maybe a -> Maybe a". The answer incorrectly states that there are six. In fact there may be more or fewer.

First off, the question is not posed sufficiently precisely. There are two kinds of ambiguity. Firstly, the function (\x -> undefined) has type a -> b, so certainly also has type Maybe a -> Maybe a. Should this also be included in the count, or do we only want the functions f for which the Haskell typechecker responds

  >gchi :type f
  f : Maybe a -> Maybe a

Secondly, do we mean arbitrary mathematical function, or functions that can be defined in Haskell? In the latter case the situation is complicated by the fact that Haskell defines a primitive function seq (first mentioned on page 150) that can add a few more functions to the list.

Allowing functions that (i) have a possibly more general type than Maybe a -> Maybe a; (ii) are Haskell definable without using seq, then the current count is 15 functions.

Applied to Nothing the function can return three values: Nothing, undefined, or Just undefined. Applied to Just x the function can return four values: Nothing, undefined, Just x, or Just undefined. That gives 12 functions. All these functions are strict. But there are also three more non-strict functions, two of which are const Nothing and const (Just undefined). The third one is trickier to spot and was found by Nick Smallbone who wrote a program to enumerate the functions:

  f x = Just (case x of Nothing -> undefined; Just v -> v)

Restricting the question to functions for which Haskell infers the specific type Maybe a -> Maybe a, there are just four functions:

  f1 x = case x of Nothing -> Nothing; Just v -> Just v
  f2 x = case x of Just v -> Just v
  f3 x = case x of Nothing -> Just undefined; Just v -> Just v
  f4 x = Just (case x of Nothing -> undefined; Just v -> v)

In each of these functions the value Just x is returned if the argument is Just x, which is necessary and sufficient to ensure a target type of Maybe a.

Thanks to Matthew Brecknall, Lennart Augustsson, Patrick Smears, John Hughes, Nick Smallbone, Ganesh Sittampalan, Jeremy Gibbons and others for helping with the exercise.

Page 45, answer to Exercise F:

The definition should be

exp x n 
        | n == 0 = 1
        | n == 1 = x
        | even n =   exp (x*x) m
        |  odd n = x*exp (x*x) m
 where m = n `div` 2

Thanks to Martin Vlk for spotting this.

Page 46, continued answer to Exercise F:

The number of multiplications is wrong; the text should read "Dick's program takes at most 2*floor (log n) multiplications, where floor returns...".

Thanks to Zachariah Levine for spotting this.

Page 49:

The Haskell 98 and Haskell 2010 reports both assert that Num is a subclass of both Eq and Show, but GHC 7.4.1 removed these superclass constraints.

Thanks to Sencer Burak Somuncuo─člu for spotting this.

Page 52:

Line 4 should read for positive x and y we have 0 <= x `mod` y < y

Thanks to Chenguang Li for spotting this.

Page 53, line 3:

until f p x should read until p f x.

Thanks to Gilbert Bonthonnou for spotting this.

Page 53, line -12:

The type of (<=) should read

(<=) :: Ord a => a -> a -> Bool

Thanks to Emmanual Viaud for spotting this.

Page 59, Exercise B:

The reference to "Exercise E" should be to "Exercise F".

Thanks to Semen Trygubenko for spotting this.

Page 59, Exercise B:

The explanations of (^^) and (**) should read: (^^) raises any fractional number to any integral power (including negative integers); and (**) takes two floating-point arguments.

Thanks to Nobuo Yamashita for spotting this.

Page 59, Exercise D:

There's a redundant parenthesis before takeWhile; compare with Clever Dick's actual solution on p52.

Thanks to Nobuo Yamashita and Carlos Suberviola Oroz for spotting this.

Page 61, Answer to Exercise A:

Replace 2 + -3 with 3 + -2.

Thanks to A Van Emmenis for spotting this.

Page 61, Answer to Exercise C:

fromInteger should be replaced (twice) by fromIntegral.

Thanks to Zhe Zhang for spotting this.

Page 62, Answer to Exercise G:

A minimal complete Ord instance requires a definition of either compare or (<=).

Thanks to Gihan Marasingha for spotting this.

Page 65:

Replace text with "When m and n are integers with m<n we can write", and change [m, n .. p] to [m, m+(n-m), m+2(n-m), ... ,m+a(n-m)], where a is the largest integer such that m+a(n-m) <= p.

Thanks to Zhe Zhang for spotting this.

Page 78, line -10:

Ramanujan's first name is "Srinivasa".

Thanks to Francisco Lieberich for spotting this.

Page 82, Exercise L:

You can't make the type synonym Pair an instance of the class Bifunctor; it would have to be a data declaration.

Thanks to Gihan Marasingha and Rui Peng for spotting this.

Page 83, line 18:

The last prompt in the GHCi session should be ghci>.

Thanks to Nobuo Yamashita for spotting this.

Page 84, Answer to Exercise G:

Strictly speaking, the two expressions should have more ellipses: 1+(1+(1+...(1+0)...)) and loop ((...(((0+1)+1)+1)...)+1,[]).

Thanks to Nobuo Yamashita for spotting this.

Page 90, line -11:

The type of digits is better as [Digit] than [Char].

Thanks to Francisco Lieberich for spotting this.

Page 100:

In the last step of the calculation, the definition of pruneBy should read

pruneBy f = f. map pruneRow . f

Thanks to Eric Yi-Hsun Huang and Nobuo Yamashita for spotting this.

Page 104:

The argument to safe should be cm, not m.

Thanks to Qiao Haiyan for spotting this.

Page 105, lines 3 and 5:

Two occurrences of filter p should be filter valid.

Thanks to Carlos Suberviola Oroz, Juan Manuel Gimeno, Paul Horsfall, and Francisco Lieberich for spotting this.

Page 107, last line:

The function transpose is used here (in the answer to Exercise A), but only defined in Exercise B, as a synonym for cols. If you read the former before the latter, it's a forward reference.

Thanks to Francisco Lieberich for spotting this.

Page 112:

Misplaced/missing parentheses in the lhs calculation of "Case m+1":

    exp x ((m + 1) + n)
=   
    exp x ((m + n) + 1)

Thanks to Torsten Grust for spotting this.

Page 119, line 9:

Missing parenthesis; the line should be

foldr f e (x:(xs ++ ys))

Thanks to Gihan Marasingha for spotting this.

Page 119:

In the penultimate block on the page, the last line should be

f x:(xs ++ ys) = (f x:xs) ++ ys

Thanks to Semen Trygubenko for spotting this.

Page 122, line -8:

Missing parenthesis in the definition of fpart:

fpart xs = read ('0':dropWhile (/= '.') xs) :: Float

Thanks to Francisco Lieberich for spotting this.

Page 126:

In the x:xs case, the last expression should be

e:scanl f (f e x) xs

Thanks to Semen Trygubenko for spotting this.

Page 127, line 11:

Remove the full stop at the end of the line:

scanl f e undefined = e : undefined

Thanks to Nobuo Yamashita for spotting this.

Page 129, line -1:

The x and xs should be in typewriter font.

Thanks to Nobuo Yamashita for spotting this.

Page 131, Exercise A:

Missing argument in the second case for mult:

mult (Succ x) y = mult x y + y

Thanks to Torsten Grust for spotting this.

Page 133:

In Exercise I, the left-hand side should read scanr f e, not scan r f e.

Thanks to Zhe Zhang for spotting this.

Page 134, line 3-4:

Variables xs and p should be in typewriter font.

Thanks to Nobuo Yamashita for spotting this.

Page 135, line -10:

Variable f should be in typewriter font.

Thanks to Nobuo Yamashita for spotting this.

Page 138:

In the Answer to Exercise F, the two occurrences of foldl g e in the right column of Case [] should be replaced by foldr g e.

Thanks to Zhe Zhang for spotting this.

Page 142, line 10:

The scan should be scanr.

Thanks to Nobuo Yamashita, Carlos Suberviola Oroz, and Francisco Lieberich for spotting this.

Page 148, line -15:

The foo 1000 should be foo2 1000.

Thanks to Nobuo Yamashita for spotting this.

Page 150, line -10:

The function foldl' is in the library Data.List, not in the prelude.

Thanks to Nobuo Yamashita and Peter Salvi for spotting this.

Page 153, line -7:

Rename variable input to x for consistency with the two later examples.

Thanks to Nobuo Yamashita and Francisco Lieberich for spotting this.

Page 157, line 3:

Should read "the minimum of a list".

Page 158, line 11:

Replace O(1) by Θ(1).

Thanks to Zhe Zhang for spotting this.

Page 158, line 16:

The final expression should be Θ(mk + m2n).

Thanks to Carlos Suberviola Oroz for spotting this.

Page 159, line 6-7:

The function cp was discussed at the end of the previous section, not the beginning of this one.

Thanks to Nobuo Yamashita for spotting this.

Page 160, line 22:

Two unbalanced parenthesis pairs: T(reverse(n)) = T(revcat(n,0))

Thanks to Nobuo Yamashita, Semen Trygubenko, Qiao Haiyan, Carlos Suberviola Oroz, and Francisco Lieberich for spotting this.

Page 162, line 9:

The left-hand side s(1,t) should be s(1,k).

Thanks to Carlos Suberviola Oroz and Francisco Lieberich for spotting this.

Page 163, line 12:

The last line of the calculation at the top of the page should read

x:labcat us (labcat vs xs)

Thanks to Peter Salvi and Nobuo Yamashita for spotting this.

Page 163, line 16:

The second argument is missing from the left-hand side in the second clause of the definition of labcat:

labcat (Node x us:vs) xs = x:labcat us (labcat vs xs)

Thanks to Carlos Suberviola Oroz, Francisco Lieberich, and Matthew Towers for spotting this.

Page 163, line -8:

Redundant parenthesis: the right-hand side should read Θ(1) + T(labcat)(1,k,n)

Thanks to Carlos Suberviola Oroz and Francisco Lieberich for spotting this.

Page 172, line 8:

The last line is missing argument xs: sortp x xs (y:us) vs

Thanks to Peter Salvi, Carlos Suberviola Oroz, and Francisco Lieberich for spotting this.

Page 172, last line:

The list to sort should be [3,4,1,2] rather than [3,4,2,1], for consistency with the answer.

Thanks to Peter Salvi, Francisco Lieberich, and Matthew Towers for spotting this.

Page 177, line 1:

The k should be a superscript: the sum is Σi=0kΘ(2k).

Thanks to Qiao Haiyan for spotting this.

Page 177, Answer to Exercise G:

Missing a closing parenthesis on the first and fourth lines of the calculation.

Thanks to Nobuo Yamashita, Carlos Suberviola Oroz, Francisco Lieberich, and Matthew Towers for spotting this.

Page 178, answer to Exercise G:

On the last line, variable z should be x. The question stipulates that part should made be local to partition, which the answer doesn't do.

Thanks to Nobuo Yamashita and Francisco Lieberich for spotting this.

Page 178, answer to Exercise I:

The σ should be a Σ, and the argument to Θ should be j rather than n: the sum is Σj=0nΘ(j).

Thanks to Qiao Haiyan, Carlos Suberviola Oroz, Francisco Lieberich, and Matthew Towers for spotting this.

Page 179, Answer to Exercise J:

The third clause of the key property should yield ys!!(k-(n+1)), and similarly in the definition of select.

Thanks to Carlos Suberviola Oroz and Francisco Lieberich for spotting this.

Page 184, line 18:

Redundant close parenthesis on the left-hand side.

Thanks to Carlos Suberviola Oroz and Matthew Towers for spotting this.

Page 186:

Replace the definition of nestl by

nestl i = concat . map (indent i)

Thanks to Dimitris Orfanos for spotting this.

Page 199, line 2:

The definitions can be in a file called Pretty.lhs or Pretty.hs, depending on whether or not the code is literate.

Thanks to Nobuo Yamashita for spotting this.

Page 199:

Haskell export syntax: ... to export all the constructors we can write Doc(..) in the export list ...

Thanks to Torsten Grust for spotting this.

Page 206, line 1:

Redundant :: in the type declaration.

Thanks to Nobuo Yamashita for spotting this.

Page 213, lines 17-19:

Replace iterate3 (2*1) by iterate3 (2*) 1 (three times).

Thanks to Zhe Zhang for spotting this.

Page 214, last line:

Should read:

foldr1 f (x:xs) = f x (foldlr1 f xs)

Thanks to Matthew Towers for spotting this.

Page 219, line 18; Page 233, Exercise I; Page 236, last line:

Replace m = pn2 by cm = pn2 (three separate times).

Thanks to Francisco Lieberich for spotting this.

Page 230, line 13:

It is x that is a doubly-linked list, not xs.

Thanks to Nobuo Yamashita and Peter Salvi for spotting this.

Page 230, line 21:

Missing closing parenthesis at the end of the line.

Thanks to Carlos Suberviola Oroz and Francisco Lieberich for spotting this.

Page 231, line -6:

Redundant curly bracket on the left-hand side.

Thanks to Peter Salvi, Carlos Suberviola Oroz, Francisco Lieberich, and Matthew Towers for spotting this.

Page 231, last line:

This is the first occurrence of foldl1; perhaps it should have been introduced on p121 along with foldr1.

Thanks to Francisco Lieberich for spotting this.

Page 232, Exercise D:

It's R.W. Hamming, not W.R. Hamming.

Thanks to Francisco Lieberich for spotting this.

Page 235, line -11:

It should be x that is compared with head ys, not xs.

Thanks to Francisco Lieberich and Matthew Towers for spotting this.

Page 245:

The second block of code should read

do {y <- lookup x alist;
    z <- lookup y blist;
    lookup z clist}
without the return.

Thanks to Randall Britten for spotting this.

Page 253:

Type vs. value:

... and in the expression runST (newSTRef True) the Haskell type checker ...

Thanks to Torsten Grust for spotting this.

Page 269, last line:

The proof obligation is:

foldr (\ n p -> add n >> p) done = add . foldr (+) 0

Thanks to Matthew Towers for spotting this.

Page 279, line 16:

The text "parser q" should read "parser q x". Also, as of GHC 7.10, it is necessary to make Parser also an instance of Functor and Applicative in order to make it a Monad.

Thanks to Matthew Towers for spotting this.

Page 280, line 7:

The type of guard is Bool -> Parser ().

Thanks to Zhe Zhang for spotting this.

Page 289:

Definition of showParen:

showParen b p = if b then...

Thanks to Torsten Grust for spotting this.

Page 290:

Invocation of showParen in the definition of shows:

shows b (Bin op e1 e2) =
  = showParen b (shows ...)

Thanks to Torsten Grust for spotting this.

Page 292:

The proposed definition of <|> should use apply rather than parse:

p <|> q = Parser (\ s -> apply p s ++ apply q s)

Thanks to Dimitris Orfanos for spotting this.

Page 295, Answer to Exercise B:

The definition of bind is broken, for several reasons. The answer should be like this:

    p >>= q = Parser (\ s -> case apply p s of
                               Nothing     -> Nothing
                               Just (x,s') -> apply (q x) s')
(Note that we also need a different definition of apply, because of the different definition of the datatype Parser.)

Thanks to Dimitris Orfanos and Nicolas Del Piano for spotting this.

Page 302:

first vs. fst in a law: fst after fork: fst . fork f g = f

Thanks to Torsten Grust for spotting this.

Page 306:

Expression representation:

(f * g) . h => Compose [Con "*" [Compose [Var "f"], Compose [Var "g"]], Var "h"]

Thanks to Torsten Grust for spotting this.

Page 307:

Type name:

ident :: Parser [Expr] -> Parser Expr

Thanks to Torsten Grust for spotting this.

Page 330, line 7:

The third equation for xmatchA is missing the sub argument.

Thanks to Paul Horsfall for spotting this.