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 29th November, 2015)

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

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 33, Line 2:

Should read

ghci> "Hello" ++ ....

Thanks to 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 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 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:

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 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 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 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 for spotting this.

Page 104:

The argument to safe should be cm, not m.

Thanks to Qiao Haiyan 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:

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 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 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 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 158, line 11:

Replace O(1) by Θ(1).

Thanks to Zhe Zhang for spotting this.

Page 163:

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

x:labcat us (labcat vs xs)

Thanks to Peter Salvi 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 186:

Replace the definition of nestl by

nestl i = concat . map (indent i)

Thanks to Dimitris Orfanos 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 213, lines 17-19:

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

Thanks to Zhe Zhang 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 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 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.