Thinking Functionally with Haskell (2 page)

I would also like to thank David Tranah, my editor at CUP, for continued advice and support. My status now is emeritus professor at the Department of Computer Science at Oxford, and I would like to thank the department and its head, Bill Roscoe, for continuing to make facilities available.

Richard Bird

Exercises

Exercise A

Express sin 3
α
in terms of sin
α
.

Answers

Answer to Exercise A

sin 3
α

= {arithmetic}

sin(2
α
+
α
)

= {since sin(
α
+
β
) =sin
α
cos
β
+ cos
α
sin
β
}

sin 2
α
cos
α
+ cos 2
α
sin
α

= {since sin 2
α
= 2 sin
α
cos
α
}

2 sin
α
cos
²
α
+ cos 2
α
sin
α

= {since cos 2
α
= cos
²
α −
sin
²
α
}

2 sin
α
cos
²
α
+(cos
²
α −
sin
²
α
)sin
α

= {since sin
²
α
+ cos
²
α
= 1}

sin
α
(3
−
4 sin
²
α
) The above proof format was, I believe, invented by Wim Feijen. It will be used throughout the book.

In a nutshell:

• Functional programming is a method of program construction that emphasises functions and their application rather than commands and their execution.
  
• Functional programming uses simple mathematical notation that allows problems to be described clearly and concisely.
  
• Functional programming has a simple mathematical basis that supports equational reasoning about the properties of programs.
  

Our aim in this book is to illustrate these three key points, using a specific functional language called Haskell.

We will use the Haskell notation

f :: X -> Y

to assert that
f
is a function taking arguments of type
X
and returning results of type
Y
. For example,

sin
:: Float -> Float

age
:: Person -> Int

add
:: (Integer,Integer) -> Integer
logBase
:: Float -> (Float -> Float)

Float
is the type of floating-point numbers, things like 3.14159, and
Int
is the type of limited-precision integers, integers
n
that lie in a restricted range such as
−2
²⁹
≤
n
< 2
²⁹
. The restriction is lifted with the type
Integer
, which is the type of unlimited-precision integers. As we will see in
Chapter 3
, numbers in Haskell come in many flavours.

In mathematics one usually writes
f
(
x
) to denote the application of the function
f
to the argument
x
. But we also write, for example, sin
θ
rather than sin(
θ
). In Haskell we can always write
f x
for the application of
f
to the argument
x
. The operation of application can be denoted using a space. If there are no parentheses the space is necessary to avoid confusion with multi-letter names:
latex
is a name but
late x
denotes the application of a function
late
to an argument
x
.

As examples,
sin 3.14
or
sin (3.14)
or
sin(3.14)
are three legitimate ways of writing the application of the function
sin
to the argument
3.14
.

Similarly,
logBase 2 10
or
(logBase 2) 10
or
(logBase 2)(10)
are all legitimate ways of writing the logarithm to base 2 of the number 10. But the expression
logBase (2 10)
is incorrect. Parentheses are needed in writing
add (3,4)
for the sum of 3 and 4 because the argument of
add
is declared above as a pair of integers and pairs are expressed with parentheses and commas.

Look again at the type of
logBase
. It takes a floating point number as argument, and returns a function as result. At first sight that might seem strange, but at second sight it shouldn’t: the mathematical functions log
₂
and log
_e
are exactly what is provided by
logBase 2
and
logBase e
.

In mathematics one can encounter expressions like logsin
x
. To the mathematician that means log(sin
x
), since the alternative (log sin)
x
doesn’t make sense. But in Haskell one has to say what one means, and one has to write
log (sin x)
because
log sin x
is read by Haskell as
(log sin) x
. Functional application in Haskell
associates
to the left in expressions and also has the highest
binding power
. (By the way,
log
is the Haskell abbreviation for
logBase e
.) Here is another example. In trigonometry one can write

sin 2
θ
= 2 sin
θ
cos
θ
.

In Haskell one has to write

sin (2*theta) = 2
sin theta
cos theta

Not only do we have to make the multiplications explicit, we also have to put in parentheses to say exactly what we mean. We could have added a couple more and written
but the additional parentheses are not necessary because functional application binds tighter than multiplication.

sin (2*theta) = 2
(sin theta)
(cos theta)

Suppose
f :: Y -> Z
and
g :: X -> Y
are two given functions. We can combine them into a new function
f . g :: X -> Z

that first applies
g
to an argument of type
X
, giving a result of type
Y
, and then applies
f
to this result, giving a final result of type
Z
. We always say that functions take
arguments
and return
results
. In fact we have
(f . g) x = f (g x)

The order of composition is from right to left because we write functions to the left of the arguments to which they are applied. In English we write ‘green pig’ and interpret adjectives such as ‘green’ as functions taking noun phrases to noun phrases. Of course, in French . . .

Let us illustrate the importance of functional composition by solving a problem. What are the 100 most common words in
War and Peace
? What are the 50 most common words in
Love’s Labours Lost
? We will write a functional program to find out. Well, perhaps we are not yet ready for a complete program, but we can construct enough of one to capture the essential spirit of functional programming.

What is given? Answer: a
text
, which is a list of characters, containing visible characters like
'B'
and
','
, and blank characters like spaces and newlines (
' '
and
'\n'
). Note that individual characters are denoted using single quotes. Thus
'f'
is a character, while
f
is a name. The Haskell type
Char
is the type of characters, and the type of lists whose elements are of type
Char
is denoted by
[Char]
. This notation is not special to characters, so
[Int]
denotes a list of integers, and
[Float -> Float]
a list of functions.

What is wanted as output? Answer: something like

This display is also a list of characters, in fact it is the list

" the: 154\n of: 50\n a: 18\n and: 12\n in: 11\n"

Lists of characters are denoted using double quotes. More on this in the exercises.

So we want to design a function,
commonWords
say, with type
commonWords :: Int -> [Char] -> [Char]

The function
commonWords n
takes a list of characters and returns a list of the
n
most common words in the list as a
string
(another name for a list of characters) in the form described above. The type of
commonWords
is written without parentheses, though we can put them in:
commonWords :: Int -> ([Char] -> [Char])

Whenever two
->
signs are adjacent in a type, the order of association is from right to left, exactly the opposite convention of functional application. So
A -> B -> C
means
A -> (B -> C)
. If you want to describe the type
(A -> B) -> C
you have to put in the parentheses. More on this in the next chapter.

Having understood precisely what is given and what is wanted, different people come up with different ways of solving the problem, and express different worries about various parts of the problem. For example, what is a ‘word’ and how do you convert a list of characters into a list of words? Are the words
"Hello"
,
"hello"
and
"Hello!"
distinct words or the same word? How do you count words? Do you count all the words or just the most common ones? And so on. Some find these details daunting and overwhelming. Most seem to agree that at some intermediate point in the computation we have to come up with a list of words and their frequencies, but how do we get from there to the final destination? Do we go through the list
n
times, extracting the word with the next highest frequency at each pass, or is there something better?

Let’s start with what a word is, and just assert that a word is a maximal sequence of characters not containing spaces or newline characters. That allows words like
"Hello!"
, or
"3*4"
or
"Thelma&Louise"
but never mind. In a text a word is identified by being surrounded by blank characters, so
"Thelma and Louise"
contains three words.

We are not going to worry about how to split a text up into a list of its component words. Instead we just assume the existence of a function
words :: [Char] -> [[Char]]

that does the job. Types like
[[Char]]
can be difficult to comprehend, but in Haskell we can always introduce
type synonyms
:

type Text = [Char]

type Word = [Char]

So now we have
words :: Text -> [Word]
, which is much easier on the brain. Of course, a text is different from a word in that the former can contain blank characters and the latter cannot, but type synonyms in Haskell do not support such subtle distinctions. In fact,
words
is a library function in Haskell, so we don’t have to define it ourselves.

There is still the issue of whether
"The"
and
"the"
denote the same or different words. They really should be the same word, and one way of achieving this is to convert all the letters in the text to lowercase, leaving everything else unchanged. To this end, we need a function
toLower :: Char -> Char
that converts uppercase letters to lowercase and leaves everything else unchanged. In order to apply this function to every character in the text we need a general function
map :: (a -> b) -> [a] -> [b]

such that
map f
applied to a list applies
f
to every element of the list. So, converting everything to lowercase is done by the function
map toLower :: Text -> Text

Good. At this point we have
words . map toLower
as the function which converts a text into a list of words in lowercase. The next task is to count the number of occurrences of each word. We could go through the list of words, checking to see whether the next word is new or has been seen before, and either starting a new count for a new word or incrementing the count for an existing word. But there is a conceptually simpler method, namely to
sort
the list of words into alphabetical order, thereby bringing all duplicated words together in the list. Humans would not do it this way, but the idea of sorting a list to make information available is probably the single most important algorithmic idea in computing. So, let us assume the existence of a function
sortWords :: [Word] -> [Word]

that sorts the list of words into alphabetical order. For example,

sortWords ["to","be","or","not","to","be"]

= ["be","be","not","or","to","to"]

Now we want to count the runs of adjacent occurrences of each word in the sorted list. Suppose we have a function
countRuns :: [Word] -> [(Int,Word)]

that counts the words. For example,

countRuns ["be","be","not","or","to","to"]

= [(2,"be"),(1,"not"),(1,"or"),(2,"to")]

The result is a list of words and their counts in alphabetical order of the words.

Now comes the key idea: we want the information in the list to be ordered not by word, but by decreasing order of count. Rather than thinking of something more clever, we see that this is just another version of sorting. As we said above, sorting is a
really
useful method in programming. So suppose we have a function
sortRuns :: [(Int,Word)] -> [(Int,Word)]