Thinking Functionally with Haskell (7 page)

If
pin :: Person -> Pin
then we need
Eq Pin
for the last instance to be correct. Of course, we don’t have to make
Person
a member of the Equality club; we can always define

samePerson :: Person -> Person -> Bool

samePerson x y = (pin x == pin y)

But we can’t use
(==)
instead of
samePerson
unless we make an instance declaration.

Here are simplified versions of two other type classes,
Ord
and
Show
:

class (Eq a) => Ord a where

(<),(<=),(>=),(>) :: a -> a -> Bool

x < y = not (x >= y)

x <= y = x == y || x < y

x >= y = x == y || x > y

x > y = not (x <= y)

class Show a where

show :: a -> String

The boolean operator
(||)
denotes disjunction:
a || b
is true only if at least one of
a
and
b
is true. We can define this operator by

(||) :: Bool -> Bool -> Bool

a || b = if a then True else b

The default definitions of the
Ord
methods are mutually dependent, so one has to provide a specific definition of at least one of them in any instance to break the dependency (unlike
Eq
where only
(/=)
was given a default definition). The type class
Ord
needs
Eq
as a
superclass
because it makes use of
(==)
in the default definitions of the four comparison operations.

The type class
Show
is used for displaying results. Haskell cannot display the result of a computation unless the type of the result is a member of
Show
. Let us explain this in a little more detail.

We begin with a mystery:

ghci> "Hello ++"\n"++ "young" ++"\n"++ "lovers"

"Hello\nyoung\nlovers"

Oh. What we wanted was

Hello

young

lovers

Why didn’t Haskell print that?

The reason is that after evaluating a wellformed expression to produce a value, Haskell applies
show
to the value to produce a string that can be printed at the terminal. Applying
show
to a value
v
produces a string that when printed looks exactly like
v
: Thus,

Printing the result involves the use of a Haskell
command

putStrLn :: String -> IO ()

The type
IO a
is a special type, the type of input–output computations that when executed have some interaction with the outside world and return a value of type
a
. If the return value is uninteresting, as with
putStrLn
, we use the null-tuple value
()
.

So, Haskell uniformly applies a show-and-put strategy to print values. Since the greeting above is already a string, we really want to miss out the show step and go straight to the put:
ghci> putStrLn ("Hello ++"\n"++ "young" ++"\n"++ "lovers")

Hello

young

lovers

Haskell provides many more commands for input–output, for reading and writing to files, for displaying graphics, and so on. Such commands have to be sequenced
correctly, and for this Haskell provides a special notation, called
do
-notation. Commands are the subject of
Chapter 10
, and what follows is simply a foretaste of things to come.

To see an example, consider the common words problem of the previous chapter. There we defined a function
commonWords :: Int -> String -> String

such that
commonWords n
took a text string and returned a string giving a table of the
n
most common words in the text. The following program reads the text from a file, and writes the output to a file. The type
FilePath
is another synonym for a list of characters:

cwords :: Int -> FilePath -> FilePath -> IO()

cwords n infile outfile

= do {text <- readFile infile;

writeFile outfile (commonWords n text);

putStrLn "cwords done!"}

Evaluating, for example

ghci> cwords 100 "c:\\WarAndPeace" "c:\\Results"

on a Windows platform will cause the file
c:\WarAndPeace
to be read, and the results printed to
c:\Results
. The program also prints a message to the terminal. The two component functions of the definition above have types

readFile
:: FilePath -> IO String

writeFile :: FilePath -> String -> IO ()

Suppose that we didn’t want to call
cwords
from within an interactive session, but to use it as a stand-alone program. Here is one way. We need to define a value for an identifier
main
of type
IO ()
. Here is such a program:

main

= do {putStrLn "Take text from where:";

infile <- getLine;

putStrLn "How many words:";

n <- getLine;

putStrLn "Put results where:";

outfile <- getLine;

text <- readFile infile;

writeFile outfile (commonWords (read n) text);

putStrLn "cwords done!" }

For an explanation of
read
see Exercise H. Suppose the common words script is stored in the file
cwords.lhs
. We can compile it with GHC, the Glasgow Haskell Compiler:
$ ghc cwords.lhs

The compiled program will be stored in the file
cwords.exe
. To run the program under Windows, type
$ cwords

and follow the instructions.

Suppose we thought that the function
commonWords
was sufficiently useful that we wanted to incorporate it into other scripts. The way to do this is to turn the common words script into a
module
. First, we rewrite the script in the following way:

module CommonWords (commonWords) where

import Data.Char (toLower)

import Data.List (sort,words)

...

commonWords :: Int -> String -> String

...

The
module
declaration is followed by the name of the module, which must begin with a capital letter. Furthermore, the script has to be stored in a file called
CommonWords.lhs
to enable Haskell to find the module (at least, if you are using literate scripts; otherwise it would be
CommonWords.hs
). Following the name of the module is a list of
exports
, the functions, types and other values you want to be able to export to other scripts. The list of exports has to be enclosed in parentheses. Here we just export one function,
commonWords
. The exports are the only things defined in the module that are visible in other modules. Omitting the export list, and the surrounding parentheses, means that everything in the module is exported.

We can then compile the module using GHC and then import it into other scripts with the declaration
import CommonWords (commonWords)

There are two major advantages of Haskell modules. One is we can structure our scripts into bite-sized chunks, separating out little groups of related functions into
separate modules. The other advantage is that the functions in a compiled module are much faster to evaluate because their definitions are compiled into machinespecific code, leading to a much slicker reduction process. GHCi is an
interpreter
rather than a compiler; it evaluates internal forms of expression that are much closer to the source language of Haskell.

The examples of
do
-notation used braces (
{
and
}
) and semicolons; these are examples of
explicit layout
. Braces and semicolons are used only to control layout and have no meaning as part of the language of Haskell expressions. We can use them in other places too:

roots :: (Float,Float,Float) -> (Float,Float)

roots (a,b,c)

| a == 0
= error "not quadratic"

| disc < 0
= error "complex roots"

| otherwise = ((-b-r)/e, (-b+r)/e)

where {disc = b*b - 4*a*c; r = sqrt d; e = 2*a}

Here the
where
clause uses explicit braces and semicolons rather than appealing to Haskell’s layout rules. Instead, we could have written

where disc = b*b - 4*a*c

r
= sqrt d

e
= 2*a

But we couldn’t have written

The layout (or
offside
) rule takes effect whenever the opening brace is omitted after the keyword
where
or
do
(and also after
let
). When this happens the indentation of the next item, whether or not on a new line, is remembered. For each subsequent line, if it is indented more, then the previous line is continued; if it is indented the same amount, then a new item begins; and if it is indented less, then the layout list is ended. At least, that’s roughly the offside rule.

The offside rule explains why there is an indentation in the declarations of type classes and instances:

class Foo a where

I am part of the class declaration.

So am I.

Now the class declaration has ended.

You can always put in braces and semicolons if in any doubt. Actually the offside rule can still cause confusion when used with
do
-notation. So the recommendation is belts, braces and semicolons.

And you thought the football offside rule was complicated.

Exercise A

On the subject of precedence, this question comes from Chris Maslanka’s puzzle page in the
Guardian
newspaper: ‘Is a half of two plus two equal to two or three?’

Exercise B

Some of the following expressions are not syntactically correct, while others are syntactically correct but do not have sensible types. Some are wellformed. Which is which? In the case of a wellformed expression, give a suitable type. Assume
double :: Int -> Int
. I suggest you don’t use a computer to check your answers, but if you do, be prepared for some strange error messages.

The expressions are:

Exercise C

In the good old days, one could write papers with titles such as

‘The morphology of prex – an essay in meta-algorithmics’

These days, journals seem to want all words capitalised:

‘The Morphology Of Prex – An Essay In Meta-algorithmics’

Write a function
modernise :: String -> String
which ensures that paper titles are capitalised as above. Here are some helpful questions to answer first: 1. The function
toLower :: Char -> Char
converts a letter to lowercase. What do you think is the name of the prelude function that converts a letter to uppercase?

2. The function
words :: String -> [Word]
was used in the previous chapter. What do you think the prelude function
unwords :: [Word] -> String

does? Hint: which, if either, of the following equations should hold?

words . unwords = id

unwords . words = id

3. The function
head :: [a] -> a
returns the head of a nonempty list, and
tail :: [a] -> [a]
returns the list that remains when the head is removed. Suppose a list has head
x
and tail
xs
. How would you reconstruct the list?

Exercise D

Beaver is an eager evaluator, while Susan is a lazy one.
¹
How many times would Beaver evaluate
f
in computing
head (map f xs)
when
xs
is a list of length
n
? How many times would Susan? What alternative to
head . map f
would Beaver prefer?

The function
filter p
filters a list, retaining only those elements that satisfy the boolean test
p
. The type of
filter
is
filter :: (a -> Bool) -> [a] -> [a]

Susan would happily use
head . filter p
for a function that finds the first element of a list satisfying
p
. Why would Beaver not use the same expression?