Thinking Functionally with Haskell (9 page)

exp x n | n == 0 = 1

| n == 1 = x

| even n = exp (x*x) m

| odd n
= x*exp (x*x) (m-1)

where m = n `div` 2

This is an example of a
divide and conquer
algorithm. Dick’s program takes
p
multiplications, where 2
^p
≤
n <
2
^p
+1
. Thus
p
= ⌊log
n
⌋, where ⌊
x
⌋ returns the
floor
of a number, the greatest integer no bigger than the number. We will consider the floor function in more detail in the following chapter.

Answer to Exercise G

The function
suffix
computes the right suffix:

If you indulged in clever arithmetic to compute
suffix
, then you should realise that Sometimes a Simple Solution is Best.

Answer to Exercise H

One solution is as follows:

The function
fromDigit
will return a numerical digit given a digit character.

Answer to Exercise I

Here is one solution:

The chapter has referred a number of times to the Haskell ‘standard prelude’. This is a collection of basic types, type classes, functions and other values that are indispensible in many programming tasks. For a complete description of the standard prelude, see
Chapter 8
of the Haskell report; alternatively, visit
www.haskell.org/onlinereport/standard-prelude.html

See
www.haskell.org
for more information on the implementation of functional languages and of Haskell in particular. An older book,
The Implementation of Functional Programming Languages
(Prentice Hall, 1987) by Simon Peyton Jones, is no longer in print, but an online version can be found at
research.microsoft.com/~simonpj/papers/slpj-book-1987

Apart from GHC there are other maintained compilers for Haskell, including UHC, the Utrecht Haskell Compiler. See the home page
cs.uu.nl/wiki/UHC
.

On the eager-versus-lazy evaluation debate, read Bob Harper’s blog article
The point of laziness
, which can be found at
existentialtype.wordpress.com/2011/04/24/

In the blog Harper enumerates some of the reasons why he prefers a strict language. But also read Lennart Augustsson’s reply to the post. Augustsson’s main point, emphasised in Exercise D, is that under strict evaluation you are forced for efficiency reasons to define most functions by explicit recursion, and therefore lose the ability to build definitions out of simple standard functions. That undercuts our
ability to reason about functions by applying general laws about their component functions.

Bob Harper is one of the authors of
The Definition of Standard ML (Revised)
(MIT Press, 1989). ML is a strict functional language. You can find an introduction to ML at
www.cs.cmu.edu/~rwh/smlbook/book.pdf

Another increasingly popular language is Agda, which is both a dependently-typed functional language and also a proof assistant; see the Agda home page
wiki.portal.chalmers.se/agda/pmwiki.php

Chris Maslanka writes a regular column in the Saturday edition of the
Guardian
newspaper.

¹
If you don’t know, google ‘lazy susan’ to discover what a lazy susan is.

Numbers in Haskell are complicated because in the Haskell world there are many different kinds of number, including:

Int
limited-precision integers in at least the range [−2
²⁹
, 2
²⁹
). Integer overflow is not detected.

Integer
arbitrary-precision integers

Rational
arbitrary-precision rational numbers
Float
single-precision floating-point numbers
Double
double-precision floating-point numbers
Complex
complex numbers (defined in
Data.Complex
)

Most programs make use of numbers in one way or another, so we have to get at least a working idea of what Haskell offers us and how to convert between the different kinds. That is what the present chapter is about.

In Haskell all numbers are instances of the type class
Num
:

class (Eq a, Show a) => Num a where

(+),(-),(*) :: a -> a -> a

negate :: a -> a

abs, signum :: a -> a

fromInteger :: Integer -> a

The class
Num
is a subclass of both
Eq
and
Show
. That means every number can be printed and any two numbers can be compared for equality. Any number can be added to, subtracted from or multiplied by another number. Any number can be
negated. Haskell allows
-x
to denote
negate x
; this is the only prefix operator in Haskell.

The functions
abs
and
signum
return the absolute value of a number and its sign. If ordering operations were allowed in
Num
(and they aren’t because, for example, complex numbers cannot be ordered), we could define

abs x
= if x < 0 then -x else x
signum x | x < 0 = -1

| x == 0 = 0

| x > 0 = 1

The function
fromInteger
is a conversion function. An integer literal such as
42
represents the application of
fromInteger
to the appropriate value of type
Integer
, so such literals have type
Num a => a
. This choice is explained further below after we have considered some other classes of number and the conversion functions between them.

The
Num
class has two subclasses, the real numbers and the fractional numbers:

class (Num a,Ord a) => Real a where

toRational :: a -> Rational

class (Num a) => Fractional a where

(/) :: a -> a -> a

fromRational :: Rational -> a

Real numbers can be ordered. The only new method in the class
Real
, apart from the comparison operations which are inherited from the superclass
Ord
, is a conversion function from elements in the class to elements of
Rational
. The type
Rational
is essentially a synonym for pairs of integers. The real number
π
is not rational, so
toRational
can only convert to an approximate rational number:
ghci> toRational pi

884279719003555 % 281474976710656

Not quite as memorable as
22 % 7
, but more accurate. The symbol
%
is used to separate the numerator and denominator of a rational number.

The fractional numbers are those on which division is defined. A complex number cannot be real but it can be fractional. A floating-point literal such as
3.149
represents the application of
fromRational
to an appropriate rational number. Thus
3.149 :: Fractional a => a

This type and the earlier type
Num a => a
for
42
explains why we can form a legitimate expression such as
42 + 3.149
, adding an integer to a floating-point number. Both types are members of the
Num
class and all numbers can be added. Consideration of
ghci> :type 42 + 3.149

42 + 3.149 :: Fractional a => a

shows that the result of the addition is also a fractional number.

One of the subclasses of the real numbers is the integral numbers. A simplified version of this class is:

class (Real a, Enum a) => Integral a where

divMod :: a -> a -> (a,a)

toInteger :: a -> Integer

The class
Integral
is a subclass of
Enum
, those types whose elements can be enumerated in sequence. Every integral number can be converted into an
Integer
through the conversion function
toInteger
. That means we can convert an integral number into any other type of number in two steps:

fromIntegral :: (Integral a, Num b) => a -> b
fromIntegral = fromInteger . toInteger

Application of
divMod
returns two values:

x `div` y = fst (x `divMod` y)

x `mod` y = snd (x `divMod` y)

The standard prelude functions
fst
and
snd
return the first and second components of a pair:

fst :: (a,b) -> a

fst (x,y) = x

snd :: (a,b) -> b

snd (x,y) = y

Mathematically,
x
div
y
= ⌊
x
/
y
⌋. We will see how to compute ⌊
x
⌋ in the following section. And
x
mod
y
is defined by
x
=(
x
div
y
) ∗
y
+
x
mod
y
For positive
x
and
y
we have 0 ≤
x
mod
y
<
x
.

Recall the function
digits2
from the first chapter, where we defined
digits2 n = (n `div` 10, n `mod` 10)

It is more efficient to say
digits2 n = n `divMod` 10
because then only one invocation of
divMod
is required. Even more briefly, we can use a section and write
digits2 = (`divMod` 10)
.

There are also other numeric classes, including the subclass
Floating
of the class
Fractional
that contains, among others, the logarithmic and trigonometric functions. But enough is enough.

The value ⌊
x
⌋, the
floor
of
x
, is defined to be the largest integer
m
such that
m
≤
x
. We define a function
floor :: Float -> Integer
for computing floors. Haskell provides such a function in the standard prelude, but it is instructive to consider our own version.

One student, call him Clever Dick, to whom this task was given came up with the following solution:

floor :: Float -> Integer

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

In words, the number is shown as a string, the string is truncated by taking only the digits up to the decimal point, and the result is read again as an integer. We haven’t met
takeWhile
yet, though Clever Dick evidently had. Clever Dick’s solution is wrong on a number of counts, and Exercise D asks you to list them.

Instead we will find the floor of a number with the help of an explicit search, and for that we will need a loop:

until :: (a -> Bool) -> (a -> a) -> a -> a
until p f x = if p x then x else until p f (f x)

The function
until
is also provided in the standard prelude. Here is an example:
ghci> until (>100) (*7) 1

343

Essentially
until f p x
computes the first element
y
in the infinite list
[x, f x, f (f x), f (f (f x)), ...]

for which
p y = True
. See the following chapter where this interpretation of
until
is made precise.

Thinking now about the design of
floor
it is tempting to start off with a case analysis, distinguishing between the cases
x
< 0 and
x
≥ 0. In the case
x
< 0 we have to find the first number
m
in the sequence −1, −2, . . . for which
m
≤
x
. That leads to – in the case of a negative argument –
floor x = until (`leq` x) (subtract 1) (-1)

where m `leq` x = fromInteger m <= x

There are a number of instructive points about this definition. Firstly, note the use of the prelude function
subtract
whose definition is
subtract x y = y-x