Thinking Functionally with Haskell: Errata (as of 6th August 2023)
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 bet==0
, notn==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 JohnsonDavies for spotting this.
 Page 25, lines 89:

"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 "backquotes".
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 besqrt 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
()
isNum 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 typea > b
, so certainly also has typeMaybe a > Maybe a
. Should this also be included in the count, or do we only want the functionsf
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 usingseq
, then the current count is 15 functions.Applied to
Nothing
the function can return three values:Nothing
,undefined
, orJust undefined
. Applied toJust x
the function can return four values:Nothing
,undefined
,Just x
, orJust undefined
. That gives 12 functions. All these functions are strict. But there are also three more nonstrict functions, two of which areconst Nothing
andconst (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 isJust x
, which is necessary and sufficient to ensure a target type ofMaybe 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 (logn ) multiplications, wherefloor 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 bothEq
andShow
, 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
andy
we have0 <= x `mod` y < y
Thanks to Chenguang Li for spotting this.
 Page 53, line 3:

until f p x
should readuntil 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 floatingpoint 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
with3 + 2
.Thanks to A Van Emmenis for spotting this.
 Page 61, Answer to Exercise C:

fromInteger
should be replaced (twice) byfromIntegral
.Thanks to Zhe Zhang for spotting this.
 Page 62, Answer to Exercise G:

A minimal complete
Ord
instance requires a definition of eithercompare
or(<=)
.Thanks to Gihan Marasingha for spotting this.
 Page 65:

Replace text with "When
m
andn
are integers withm<n
we can write", and change[m, n .. p]
to[m, m+(nm), m+2(nm), ... ,m+a(nm)]
, wherea
is the largest integer such thatm+a(nm) <= 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 classBifunctor
; it would have to be adata
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)...))
andloop ((...(((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 readpruneBy f = f. map pruneRow . f
Thanks to Eric YiHsun Huang and Nobuo Yamashita for spotting this.
 Page 104:

The argument to
safe
should becm
, notm
.Thanks to Qiao Haiyan for spotting this.
 Page 105, lines 3 and 5:

Two occurrences of
filter p
should befilter valid
.Thanks to Carlos Suberviola Oroz, Juan Manuel Gimeno, Paul Horsfall, and Francisco Lieberich for spotting this.
 Page 106:

The first equation in Exercise C should be
any p = not . all (not . p)
Thanks to Akiel Khan 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 forcols
. 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
[]
case, in the third step, only rulemap.1
is used; and in thex:xs
case, in the third step, only rulemap.2
is used. Thanks to John Tasto for spotting this.  Page 126:

In the
x:xs
case, the last expression should bee: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
andxs
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 lefthand side should read
scanr f e
, notscan r f e
.Thanks to Zhe Zhang for spotting this.
 Page 134, line 34:

Variables
xs
andp
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 byfoldr g e
.Thanks to Zhe Zhang for spotting this.
 Page 142, line 10:

The
scan
should bescanr
.Thanks to Nobuo Yamashita, Carlos Suberviola Oroz, and Francisco Lieberich for spotting this.
 Page 148, line 15:

The
foo 1000
should befoo2 1000
.Thanks to Nobuo Yamashita for spotting this.
 Page 150, line 10:

The function
foldl'
is in the libraryData.List
, not in the prelude.Thanks to Nobuo Yamashita and Peter Salvi for spotting this.
 Page 152, line 5:

sumlem
should besumlen
.Thanks to Jingjie Yang for spotting this.
 Page 153, line 7:

Rename variable
input
tox
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 + m^{2}n ).Thanks to Carlos Suberviola Oroz for spotting this.
 Page 159, line 67:

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 lefthand side
s(1,t) should bes(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 lefthand 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 righthand 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) vsThanks 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=0}^{k}Θ(2^{k}) .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 H:

On the last line, variable
z
should bex
. The question stipulates thatpart
should made be local topartition
, 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 bej rather thann : the sum isΣ_{j=0}^{n}Θ(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 ofselect
.Thanks to Carlos Suberviola Oroz and Francisco Lieberich for spotting this.
 Page 184, line 18:

Redundant close parenthesis on the lefthand side.
Thanks to Carlos Suberviola Oroz and Matthew Towers for spotting this.
 Page 186:

Replace the definition of
nestl
bynestl 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
orPretty.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 1719:

Replace
iterate3 (2*1)
byiterate3 (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 = p_{n}^{2} byc_{m} = p_{n}^{2} (three separate times).Thanks to Francisco Lieberich for spotting this.
 Page 230, line 13:

It is
x
that is a doublylinked list, notxs
.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 lefthand 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 withfoldr1
.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 withhead ys
, notxs
.Thanks to Francisco Lieberich and Matthew Towers for spotting this.
 Page 236, Answer to Exercise I:

The proof sketch is wrong; for example, there's no easy way to obtain
crs 3 = 4:6:8:9:10:12:14:15:16:18:20:21:22:24:25:undefined
fromcrs 2 = 4:6:8:9:undefined
and(let p = 5 in map (p*) [p..]) = [25,30..]
Thanks to Francisco Lieberich for spotting this. Jeremy Gibbons has blogged about this. In fact,
crs 3
can be obtained fromcrs 2
alone…  Page 245:

The second block of code should read
do {y < lookup x alist; z < lookup y blist; lookup z clist}
without thereturn
.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 262:

The definition should read:
sort xs = concat [ replicate c x  (x,c) < assocs (count xs) ]
Thanks to Mani Tadayon 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 "parserq x
". Also, as of GHC 7.10, it is necessary to makeParser
also an instance ofFunctor
andApplicative
in order to make it aMonad
.Thanks to Matthew Towers for spotting this.
 Page 280, line 7:

The type of
guard
isBool > 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 ofshows
:shows b (Bin op e1 e2) = = showParen b (shows ...)
Thanks to Torsten Grust for spotting this.
 Page 292:

The proposed definition of
<>
should useapply
rather thanparse
: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 ofapply
, because of the different definition of the datatypeParser
.)Thanks to Dimitris Orfanos and Nicolas Del Piano for spotting this.
 Page 302:

first
vs.fst
in a law:fst
afterfork
: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 thesub
argument.Thanks to Paul Horsfall for spotting this.