Thinking Functionally with Haskell (10 page)

We have to use
subtract 1
because
(-1)
is
not
a section but the number −1 (look at the third argument of
until
).

Secondly, why have we used
`leq`
when the alternative
(<=)
seems perfectly adequate? The answer is that
(<=)
has the type
(<=) :: Num a => a -> a -> Bool

In particular the two arguments of
(<=)
have to have the same type. But we want
leq :: Integer -> Float -> Bool

and the two arguments have different numeric types. We therefore need to convert integers to floats using
fromInteger
. Appreciation of the need for conversion functions in some situations is one of the key points to understand about Haskell arithmetic.

Finally, note that
(`leq` x)
is not the same as
(leq x)
:

(leq x) y = leq x y

(`leq` x) y = y `leq` x = leq y x

It is easy to make this mistake.

If you don’t like the subsidiary definition, you can always write

floor x = until ((<=x) . fromInteger) (subtract 1) (-1)
In this version we have
inlined
the definition of
(`leq` x)
.

We still have to deal with the case
x
≥ 0. In this case we have to look for the first integer
n
such that
x
<
n
+1. We can do this by finding the first integer
n
such that
x
<
n
and subtracting 1 from the answer. That leads to

floor x = until (x `lt` ) (+1) 1 - 1

where x `lt` n = x < fromInteger n

Putting the two pieces together, we obtain

(Question: why do we not have to write
x < fromInteger 0
in the first line?) The real problem with this definition, apart from the general ugliness of a case distinction and the asymmetry of the two cases, is that it is very slow: it takes about |
x
| steps (|
x
| is the mathematician’s way of writing
abs x
) to deliver the result.

Binary search

A better method for computing
floor
is to first find integers
m
and
n
such that
m
≤
x
<
n
and then shrink the interval (
m
,
n
) to a unit interval (one with
m
+1 =
n
) that contains
x
. Then the left-hand bound of the interval can be returned as the result. That leads to

floor :: Float -> Integer

floor x = fst (until unit (shrink x) (bound x))

where unit (m,n) = (m+1 == n)

The value
bound x
is some pair (
m
,
n
) of integers such that
m
≤
x
<
n
. If (
m
,
n
) is not a unit interval, then
shrink x (m,n)
returns a new interval of strictly smaller size that still bounds
x
.

Let us first consider how to shrink a non-unit interval (
m
,
n
) containing
x
, so
m
≤
x
<
n
. Suppose
p
is any integer that satisfies
m
<
p
<
n
. Such a
p
exists since (
m
,
n
) is not a unit interval. Then we can define

type Interval = (Integer,Integer)

shrink :: Float -> Interval -> Interval

shrink x (m,n) = if p `leq` x then (p,n) else (m,p)
where p = choose (m,n)

How should we define
choose
?

Two possible choices are
choose (m,n) = m+1
or
choose (m,n) = n-1
for both reduce the size of an interval. But a better choice is

choose :: Interval -> Integer

choose (m,n) = (m+n) `div` 2

With this choice the size of the interval is halved at each step rather than reduced by 1.

However, we need to check that
m
< (
m
+
n
) div 2 <
n
in the case
m
+ 1 ≠
n
. The reasoning is:
m
< (
m
+
n
) div 2 <
n

≡ {ordering on integers}

m
+ 1 ≤ (
m
+
n
) div 2 <
n

≡ {since (
m
+
n
) div 2 = ⌊(
m
+
n
)/2⌋}

m
+ 1 ≤ (
m
+
n
)/2 <
n

≡ {arithmetic}

m
+ 2 ≤
n
∧
m
<
n

≡ {arithmetic}

m
+ 1 <
n

Finally, how should we define
bound
? We can start off by defining

bound :: Float -> Interval

bound x = (lower x, upper x)

The value
lower x
is some integer less than or equal to
x
, and
upper x
some integer greater than
x
. Instead of using linear search to discover these values, it is better to use

lower :: Float -> Integer

lower x = until (`leq` x) (*2) (-1)

upper :: Float -> Integer

upper x = until (x `lt`) (*2) 1

For a fast version of
bound
it is better to double at each step rather than increase or decrease by 1. For example, with
x
= 17.3 it takes only seven comparisons to compute the surrounding interval (−1, 32), which is then reduced to (17, 18) in a further five steps. In fact, evaluating both the upper and lower bounds takes time proportional to log|
x
| steps, and the whole algorithm takes at most twice this time. An algorithm that takes logarithmic time is much faster than one that takes linear time.

The standard prelude defines
floor
in the following way:

floor x = if r < 0 then n-1 else n

where (n,r) = properFraction x

The function
properFraction
is a method in the
RealFrac
type class (a class we haven’t discussed and whose methods deal with truncating and rounding numbers). It splits a number
x
into its integer part
n
and its fractional part
r
, so
x
=
n
+
r
. Now you know.

Haskell does not provide a type for the natural numbers, that is, the nonnegative integers. But we can always define such a type ourselves:
data Nat = Zero | Succ Nat

This is an example of a
data declaration
. The declaration says that
Zero
is a value of
Nat
and that
Succ n
is also a value of
Nat
whenever
n
is. Both
Zero
and
Succ
are called
data constructors
and begin with a capital letter. The type of
Zero
is
Nat
and the type of
Succ
is
Nat -> Nat
. Thus each of
Zero, Succ Zero, Succ (Succ Zero), Succ (Succ (Succ Zero))
is an element of
Nat
.

Let us see how to program the basic arithmetical operations by making
Nat
a fully paid-up member of the
Num
class. First, we have to make
Nat
an instance of
Eq
and
Show
:

instance Eq Nat where

Zero == Zero
= True

Zero == Succ n
= False
Succ m == Zero
= False
Succ m == Succ n
= (m == n)

These definitions make use of
pattern matching
. In particular, the definition of
show
makes use of three patterns,
Zero
,
Succ Zero
and
Succ (Succ n)
. These patterns are different from one another and together cover all the elements of
Nat
apart from ⊥.

Alternatively, we could have declared

data Nat = Zero | Succ Nat deriving (Eq,Ord,Show)
As we said in Exercise E of the previous chapter, Haskell is smart enough to construct automatically instances of some standard classes, including
Eq
,
Ord
and
Show
.

Now we can install
Nat
as a numeric type:

instance Num Nat where

m + Zero
= m

m + Succ n = Succ (m+n)

m * Zero
= Zero

m * (Succ n) = m * n + m

abs n
= n

signum Zero
= Zero

signum (Succ n) = Succ Zero

m - Zero
= m

Zero - Succ n
= Zero

Succ m - Succ n = m - n

fromInteger x

| x <= 0
= Zero

| otherwise = Succ (fromInteger (x-1))

We have defined subtraction as a total operation:
m
−
n
= 0 if
m
≤
n
. Of course, the arithmetic operations on
Nat
are horribly slow. And each number takes up a lot of space.

We have said that there is a value ⊥ of every type. Thus
undefined :: a
for all types
a
. Since
Succ
is, by definition, a non-strict function, the values
undefined, Succ undefined, Succ (Succ undefined), ...

are all different and all members of
Nat
. To be honest, these partial numbers are not very useful, but they are there. You can think of
Succ undefined
as being a number about which we know only that it is at least 1:
ghci> Zero == Succ undefined

False

ghci> Succ Zero == Succ undefined

*** Exception: Prelude.undefined

There is also one further number in
Nat
:

Thus

ghci> Zero == infinity

False

ghci> Succ Zero == infinity

False

and so on.

In summary, the elements of
Nat
consist of the finite numbers, the partial numbers and the infinite numbers (of which there is only one). We shall see that this is true of other data types: there are the finite elements of the type, the partial elements and the infinite elements.

We could have chosen to make the constructor
Succ
strict. This is achieved by declaring
data Nat = Zero | Succ !Nat

The annotation
!
is known as
strictness flag
. With such a declaration, we have for example
ghci> Zero == Succ undefined

*** Exception: Prelude.undefined

This time, evaluating the equality test forces the evaluation of both sides, and the evaluation of
Succ undefined
raises an error message. Making
Succ
strict collapses the natural numbers into just the finite numbers and one undefined number.

Exercise A

Which of the following expressions denote 1?

-2 + 3, 3 + -2, 3 + (-2), subtract 2 3, 2 + subtract 3

In the standard prelude there is a function
flip
defined by
flip f x y = f y x

Express
subtract
using
flip
.

Exercise B

Haskell provides no fewer than three ways to define exponentiation:

(^)
:: (Num a, Integral b) => a -> b -> a
(^^) :: (Fractional a, Integral b) => a -> b -> a
(**) :: (Floating a) => a -> a -> a

The operation
(^)
raises any number to a nonnegative integral power;
(^^)
raises any number to any integral power (including negative integers); and
(**)
takes two fractional arguments. The definition of
(^)
basically follows Dick’s method of the previous chapter (see Exercise E). How would you define
(^^)
?

Exercise C

Could you define
div
in the following way?

Exercise D

Consider again Clever Dick’s solution for computing
floor
:

floor :: Float -> Integer

floor = read . (takeWhile (/= '.') . show

Why doesn’t it work?

Consider the following mini-interaction with GHCi:

ghci> 12345678.0 :: Float

1.2345678e7

Haskell allows the use of so-called
scientific notation
, also called
exponent notation
, to describe certain floating-point numbers. For example the number above denotes 1.2345678 ∗ 10
⁷
. When the number of digits of a floating-point number is sufficiently large, the number is printed in this notation. Now give another reason why Clever Dick’s solution doesn’t work.