Thinking Functionally with Haskell (8 page)

Instead, Beaver would probably define something like

The function
null
returns
True
on an empty list, and
False
otherwise. When evaluated, the expression
error message
stops execution and prints the string
message
at the terminal, so its value is ⊥. Complete the right-hand side of Beaver’s definition.

What alternative might Beaver prefer to
head . filter p . map f
?

Exercise E

The type
Maybe
is declared in the standard prelude as follows:
data Maybe a = Nothing | Just a

deriving (Eq, Ord)

This declaration uses a
deriving
clause. Haskell can automatically generate instances of some standard type classes for some data declarations. In the present case the deriving clause means that we don’t have to go through the tedium of writing

instance (Eq a) => Eq (Maybe a)

Nothing == Nothing = True

Nothing == Just y
= False

Just x == Nothing
= False

Just x == Just y
= (x == y)

instance (Ord a) => Ord (Maybe a)

Nothing <= Nothing = True

Nothing <= Just y
= True

Just x <= Nothing
= False

Just x <= Just y
= (x <= y)

The reason why
Nothing
is declared to be less than
Just y
is simply because the constructor
Nothing
comes before the constructor
Just
in the data declaration for
Maybe
.

The reason why the
Maybe
type is useful is that it provides a systematic way of handling failure. Consider again the function
first p = head . filter p

of the previous exercise. Both Eager Beaver and Lazy Susan produced versions of this function that stopped execution and returned an error message when
first p
was applied to the empty list. That’s not very satisfactory. Much better is to define
first :: (a -> Bool) -> [a] -> Maybe a

Now failure is handled gracefully by returning
Nothing
if there is no element of the list that satisfies the test.

Give a suitable definition of this version of
first
.

Finally, count the number of functions with type
Maybe a -> Maybe a
.

Exercise F

Here is a function for computing
x
to the power
n
, where
n
≥ 0:

How many multiplications does it take to evaluate
exp x n
? Dick, a clever programmer, claims he can compute
exp x n
with far fewer multiplications:

exp x n | n == 0
= 1

| n == 1 = x

| even n = ...

| odd n
= ...

Fill in the dots and say how many multiplications it takes to evaluate the expression
exp x n
by Dick’s method, assuming 2
^p
≤
n <
2
^p
+1
.

Exercise G

Suppose a date is represented by three integers (
day, month, year
). Define a function
showDate :: Date -> String
so that, for example,

showDate (10,12,2013) = "10th December, 2013"

showDate (21,11,2020) = "21st November, 2020"

You need to know that
Int
is a member of the type class
Show
, so that
show n
produces a string that is the decimal representation of the integer
n
.

Exercise H

The credit card company Foxy issues cards with ten-digit card-identification numbers (CINs). The first eight digits are arbitrary but the number formed from the last two digits is a checksum equal to the sum of the first eight digits. For example, “6324513428” is a valid CIN because the sum of the first eight digits is 28.

Construct a function
addSum :: CIN -> CIN
that takes a string consisting of eight digits and returns a string of ten digits that includes the checksum. Thus
CIN
is a type synonym for
String
, though restricted to strings of digits. (Note that Haskell type synonyms cannot enforce type constraints such as this.) You will need to convert between a digit character and the corresponding number. One direction is easy: just use
show
. The other direction is also fairly easy:

getDigit :: Char -> Int

getDigit c = read [c]

The function
read
is a method of the type class
Read
and has type
read :: Read a => String -> a

The type class
Read
is dual to
Show
and
read
is dual to
show
. For example,
ghci> read "123" :: Int

123

ghci> read "123" :: Float

123.0

The function
read
has to be supplied with the type of the result. One can always add
type annotations
to expressions in this way.

Now construct a function
valid :: CIN -> Bool
that checks whether an identification number is valid. The function
take
might prove useful.

Exercise I

By definition a
palindrome
is a string that, ignoring punctuation symbols, blank characters and whether or not a letter is in lowercase or uppercase, reads the same forwards and backwards. Write an interactive program
palindrome :: IO ()

which, when run, conducts an interactive session, such as

ghci> palindrome

Enter a string:

Madam, I'm Adam

Yes!

ghci> palindrome

Enter a string:

A Man, a plan, a canal - Suez!

No!

ghci> palindrome

Enter a string:

Doc, note I dissent. A fast never prevents a fatness.

I diet on cod.

Yes!

The function
isAlpha :: Char -> Bool
tests whether a character is a letter, and
reverse :: [a] -> [a]
reverses a list. The function
reverse
is provided in the standard prelude and
isAlpha
can be imported from the library
Data.Char
.

Answer to Exercise A

The answer to Maslanka’s puzzle is ‘Yes!’ This little puzzle has fooled a number of distinguished computer scientists.

Answer to Exercise B

My GHCi session produced (with explanations added):

ghci> :type [0,1)

:1:5: parse error on input `)'

GHCi knows that
')'
is wrong, though it is not smart enough to suggest
']'
.

ghci> :type double -3

:1:9:

No instance for (Num (Int -> Int))

arising from the literal `3'

Possible fix: add an instance declaration for

(Num (Int -> Int))

In the second argument of `(-)', namely `3'

In the expression: double - 3

The explanation of the error message is that numerical subtraction
(-)
has type
Num a => a -> a
. For
double - 3
to be wellformed (yes, it was typed as
double -3
but the spaces are not significant here),
double
has to be a number, so the class instance
Num (Int -> Int)
is required. But there isn’t one: you cannot sensibly subtract a number from a function.

ghci> double (-3)

-6

ghci> double double 0

:1:1:

The function `double' is applied to two arguments,

but its type `Int -> Int' has only one

In the expression: double double 0

In an equation for `it': it = double double 0

Most of GHCi’s error message is clear.

ghci> if 1==0 then 2==1

:1:18: parse error (possibly incorrect indentation)
Conditional expressions are incomplete without an ‘else’ clause.

ghci> "++" == "+" ++ "+"

True

Both sides are wellformed and denote the same list.

ghci> [(+),(-)]

:1:1:

No instance for (Show (a0 -> a0 -> a0))

arising from a use of `print'

Possible fix:

add an instance declaration for

(Show (a0 -> a0 -> a0))

In a stmt of an interactive GHCi command: print it

To display the value
[(+),(-)]
we have to be able to show its elements. But no way of showing functions has been provided.

ghci> :type [[],[[]],[[[]]]]

[[],[[]],[[[]]]] :: [[[[a]]]]

To explain, let the main list have type
[b]
. The first element is a list, so
b=[c]
. The second element is a list of lists, so
c=[d]
. The third element is a list of lists of lists, so
d=[a]
.

ghci> concat ["tea","for",'2']

:1:21:

Couldn't match expected type `[Char]'

with actual type `Char'

In the expression: '2'

In the first argument of `concat',

namely `["tea", "for", '2']'

In the expression: concat ["tea", "for", '2']

The first two elements of the list have type
[Char]
, but the last has type
Char
and that is not allowed.

ghci> concat ["tea","for","2"]

"teafor2"

Answer to Exercise C

1.
toUpper
, of course.

2. Concatenates the words, putting a single space between them. We have

words . unwords = id

but not
unwords . words = id
.

3.
[x] ++ xs
.

We will see another way of writing
capitalise
in
Chapter 4
.

Answer to Exercise D

Computing
head (map f xs)
takes
n
evaluations of
f
under eager evaluation, but only one under lazy evaluation. Beaver would have to exploit the identity
head . map f = f . head
.

Instead of defining
first p = head . filter p
, Beaver might define

first :: (a -> Bool) -> [a] -> a

first p xs | null xs = error "Empty list"

| p x = x

| otherwise = first p (tail xs)

where x = head xs

Instead of defining
first p f = head . filter p . map f
, Beaver might define

first :: (b -> Bool) -> (a -> b) -> [a] -> b

first p f xs | null xs = error "Empty list"

| p x = x

| otherwise = first p f (tail xs)

where x = f (head xs)

The point is that with eager evaluation most functions have to be defined using explicit recursion, not in terms of useful component functions like
map
and
filter
.

Answer to Exercise E

Lazy Susan would probably write

As to the number of functions of type
Maybe a -> Maybe a
, there are just six. Applied to
Nothing
the function can only return
Nothing
or
undefined
. Applied to
Just x
the function can only return
Nothing
or
Just x
or
undefined
. The point is that we know absolutely nothing about the underlying type, so no new values can be invented. That makes six possible functions in all.

Answer to Exercise F

It takes
n-1
multiplications to evaluate
exp x n
. Dick’s method is to exploit the identities
x
^2
m
=(
x
²
)
^m
and
x
^2
m
+1
=
x
(
x
²
)
^m
to obtain a recursive definition: