Thinking Functionally with Haskell (11 page)

Exercise E

The function
isqrt :: Float -> Integer
returns the floor of the square root of a (nonnegative) number. Following the strategy of
Section 3.3
, construct an implementation of
isqrt x
that takes time proportional to log
x
steps.

Exercise F

Haskell provides a function
sqrt :: Floating a => a -> a
that gives a reasonable approximation to the square root of a (nonnegative) number. But, let’s define our own version. If
y
is an approximation to
then so is
x
/
y
. Moreover, either
What is a better approximation to
than either
y
or
x
/
y
? (Yes, you have just rediscovered Newton’s method for finding square roots.) The only remaining problem is to decide when an approximation
y
is good enough. One possible test is |
y
²
−
x
| <
ε
, where |
x
| returns the absolute value of
x
and
ε
is a suitably small number. This test guarantees an
absolute
error of at most
ε
. Another test is |
y
²
−
x
| <
ε
∗
x
, which guarantees a
relative
error of at most
ε
. Assuming that numbers of type
Float
are accurate only to six significant figures, which of these two is the more sensible test, and what is a sensible value for
ε
?

Hence construct a definition of
sqrt
.

Exercise G

Give an explicit instance of
Nat
as a member of the type class
Ord
. Hence construct a definition of
divMod :: Nat -> Nat -> (Nat,Nat)

Answer to Exercise A

All except
2 + -3
and
2 + subtract 3
, neither of which are well-formed. We have
subtract = flip (-)
.

Answer to Exercise B

x ^^ n = if 0 <= n then x^n else 1/(x ^ (negate n))
Answer to Exercise C

No. You would have to write

Answer to Exercise D

Clever Dick’s function gives
floor (-3.1) = -3
when the answer should be
-4
. And if you tried to repair his solution by subtracting 1 if the solution was negative, you would have
floor (-3.0) = -4
when the answer should be
-3
. Ugh!

Also, Clever Dick’s solution has
floor 12345678.0 = 1
because the argument is shown as
1.2345678e7
.

Answer to Exercise E

The functions
`leq`
and
`lt`
were defined in
Section 3.3
. Note the parentheses in the expressions
(p*p) `leq` x
and
x `lt` (n*n)
. We didn’t state an order of association for
`leq`
and
`lt`
, so without parentheses these two expressions
would have been interpreted as the ill-formed expressions
p * (p `leq` x)
and
(x `lt` n) * n
. (I made just this mistake when first typing in the solution.)
Answer to Exercise F

A better approximation to
than either
y
or
x
/
y
is (
y
+
x
/
y
)/2. The relative-error test is the more sensible one, and the program is

sqrt :: Float -> Float

sqrt x = until goodenough improve x

where goodenough y = abs (y*y-x) < eps*x

improve y
= (y+x/y)/2

eps
= 0.000001

Answer to Exercise G

It is sufficient to define
(<)
:

Now we can define

The primary source book for computer arithmetic is
The Art of Computer Programming, Volume 2: Semi-numerical Algorithms
(Addison-Wesley, 1998) by Don Knuth. The arithmetic of floors and other simple numerical functions is studied in depth in
Concrete Mathematics
(Addison-Wesley, 1989) by Don Knuth, Ronald Graham and Oren Patashnik.

Lists are the workhorses of functional programming. They can be used to fetch and carry data from one function to another; they can be taken apart, rearranged and combined with other lists to make new lists. Lists of numbers can be summed and multiplied; lists of characters can be read and printed; and so on. The list of useful operations on lists is a long one. This chapter describes some of the operations that occur most frequently, though one particularly important class will be introduced only in
Chapter 6
.

As we have seen, the type
[a]
denotes lists of elements of type
a
. The empty list is denoted by
[]
. We can have lists over any type but we cannot mix different types in the same list. As examples,

List notation, such as
[1,2,3]
, is in fact an abbreviation for a more basic form
1:2:3:[]

The operator
(:) :: a -> [a] -> [a]
, pronounced ‘cons’, is a constructor for lists. It associates to the right so there is no need for parentheses in the above expression. It has no associated definition, which is why it is a constructor. In other words, there are no rules for simplifying an expression such as
1:2:[]
. The
operator
(:)
is non-strict in both arguments – more precisely, it is non-strict and returns a non-strict function. The expression
undefined : undefined

may not be very interesting, but we do know it is not the empty list. In fact, that is the only thing we do know about it. Note that the two occurrences of
undefined
have different types in this expression.

The empty list
[]
is also a constructor. Lists can be introduced as a Haskell data type with the declaration
data List a = Nil | Cons a (List a)

The only difference is that
List a
is written
[a]
,
Nil
is written
[]
and
Cons
is written
(:)
.

According to this declaration, every list of type
[a]
takes one of three forms:

• The undefined list
  undefined :: [a]
  ;
  
• The empty list
  [] :: [a]
  ;
  
• A list of the form
  x:xs
  where
  x :: a
  and
  xs :: [a]
  .
  

As a result there are three kinds of list:

• A
  finite
  list, which is built from
  (:)
  and
  []
  ; for example,
  1:2:3:[]
  
• A
  partial
  list, which is built from
  (:)
  and
  undefined
  ; for example, the list
  filter (<4) [1..]
  is the partial list
  1:2:3:undefined
  . We know there is no integer after 3 that is less than 4, but Haskell is an evaluator, not a theorem prover, so it ploughs away without success looking for more answers.
  
• An
  infinite
  list, which is built from
  (:)
  alone; for example,
  [1..]
  is the infinite list of the nonnegative integers.
  

All three kinds of list arise in everyday programming.
Chapter 9
is devoted to exploring the world of infinite lists and their uses. For example, the prelude function
iterate
returns an infinite list:

iterate :: (a -> a) -> a -> [a]

iterate f x = x:iterate f (f x)

In particular,
iterate (+1) 1
is an infinite list of the positive integers, a value we can also write as
[1..]
(see the following section).

As another example,

returns the first perfect number, namely 6, even though nobody currently knows whether
filter perfect [1..]
is an infinite or partial list.

Finally, we can define

until p f = head . filter p . iterate f

The function
until
was used to compute floors in the previous chapter. As this example demonstrates, functions that seem basic in programming are often composed of even simpler functions. A bit like protons and quarks.