Read Thinking Functionally with Haskell Online
Authors: Richard Bird
We could also have used guarded equations:
link h | h < 100 = " and "
| otherwise = " "
Sometimes one is more readable, sometimes the other. The names
if
,
then
and
else
, along with some others, are
reserved words
in Haskell, which means that we cannot use them as names for things we want to define.
Notice how the definition of
convert6
has been constructed in terms of the simpler function
convert3
, which in turn has been defined in terms of the even simpler function
convert2
. That is often the way with function definitions. In this example consideration of the simpler cases is not wasted because these simple cases can be used in the final definition.
One more thing: we have now named the function we are after as
convert6
, but we started off by saying the name should be
convert
. No problem:
> convert :: Int -> String
> convert = convert6
What we would like to do now is actually use the computer to apply
convert
to some arguments. How?
If you visit the site
www.haskell.org
, you will see how to download
The Haskell Platform
. This is a large collection of tools and packages that can be used to run Haskell scripts. The platform comes in three versions, one for each of Windows, Mac and Linux. We deal only with the Windows version, the others being similar.
One of the tools is an interactive calculator, called GHCi. This is short for
Glasgow Haskell Compiler Interpreter
. The calculator is available as a Windows system called WinGHCi. If you open this window, you will get something like
GHCi, version 7.6.3:
http://www.haskell.org/ghc/
:? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Prelude>
The prompt
Prelude>
means that the standard library of prelude functions, predeclared types and other values is loaded. You can now use GHCi as a supercalculator:
Prelude> 3^5
243
Prelude> import Data.Char
Prelude Data.Char> map toLower "HELLO WORLD!"
"hello world!"
Prelude Data.Char>
The function
toLower
resides in the library
Data.Char
. After importing this library you have access to the functions defined in the library. Note that the prompt changes and now indicates the libraries that have been loaded. Such prompts can grow in size very quickly. But we can always change the prompt:
Prelude> :set prompt ghci>
ghci>
For brevity we will use this prompt throughout the book.
You can load a script,
Numbers2Words.lhs
say, that contains the definition of
convert
as follows:
ghci> :load "Numbers2Words.lhs"
[1 of 1] Compiling Main ( Numbers2Words.lhs, interpreted )
Ok, modules loaded: Main.
ghci>
We will explain what modules are in the next chapter. Now you can type, for example,
ghci> convert 301123
"three hundred and one thousand one hundred and twenty-three" ghci>
We end the chapter with some exercises. These contain additional points of interest
and should be regarded as an integral part of the text. The same is true for all subsequent chapters, so please read the questions even if you do not answer them. The answers are given afterwards.
Exercise A
Consider the function
double :: Integer -> Integer
double x = 2*x
that doubles an integer. What are the values of the following expressions?
map double [1,4,4,3]
map (double . double) [1,4,4,3]
map double []
Suppose
sum :: [Integer] -> Integer
is a function that sums a list of integers. Which of the following assertions are true and why?
sum . map double
= double . sum
sum . map sum
= sum . concat
sum . sort
= sum
You will need to recall what the function
concat
does. The function
sort
sorts a list of numbers into ascending order.
Exercise B
In Haskell, functional application takes precedence over every other operator, so
double 3+4
means
(double 3)+4
, not
double (3+4)
. Which of the following expressions is a rendering of sin
2
θ
into Haskell?
sin^2 theta
sin theta^2
(sin theta)^2
(Exponentiation is denoted by
(^)
.) How would you express sin 2
θ
/2
π
as a wellformed Haskell expression?
Exercise C
As we said in the text, a character,
i.e.
an element of
Char
, is denoted using single quotes, and a string is denoted using double quotes. In particular the string
"Hello World!"
is just a much shorter way of writing the list
['H','e','l','l','o',' ','W','o','r','l','d','!']
General lists can be written with brackets and commas. (By the way, parentheses are round, brackets are square, and braces are curly.) The expressions
'H'
and
"H"
therefore have different types. What are they? What is the difference between
2001
and
"2001"
?
The operation
++
concatenates two lists. Simplify
[1,2,3] ++ [3,2,1]
"Hello" ++ " World!"
[1,2,3] ++ []
"Hello" ++ "" ++ "World!"
Exercise D
In the common words example we started off by converting every letter in the text to lowercase, and then we computed the words in the text. An alternative is to do things the other way round, first computing the words and then converting each letter in each word to lowercase. The first method is expressed by
words . map toLower
. Give a similar expression for the second method.
Exercise E
An operator ⊕ is said to be
associative
if
x
⊕ (
y
⊕
z
) = (
x
⊕
y
) ⊕
z
. Is numerical addition associative? Is list concatenation associative? Is functional composition associative? Give an example of an operator on numbers that is not associative.
An element
e
is said to be an
identity element
of ⊕ if
x
⊕
e
=
e
⊕
x
=
x
for all
x
. What are the identity elements of addition, concatenation and functional composition?
Exercise F
My wife has a book with the title
EHT CDOORRSSW AAAGMNR ACDIINORTY
.
It contains lists of entries like this:
6-letter words
--------------
...
eginor: ignore,region
eginrr: ringer
eginrs: resign,signer,singer
...
Yes, it is an anagram dictionary. The letters of the anagrams are sorted and the results are stored in dictionary order. Associated with each anagram are the English words with the same letters. Describe how you would go about designing a function
anagrams :: Int -> [Word] -> String
so that
anagrams n
takes a list of English words in alphabetical order, extracts just the
n
-letter words and produces a string that, when displayed, gives a list of the anagram entries for the
n
-letter words. You are not expected to be able to define the various functions; just give suitable names and types and describe what each of them is supposed to do.
Exercise G
Let’s end with a song:
One man went to mow
Went to mow a meadow
One man and his dog
Went to mow a meadow
Two men went to mow
Went to mow a meadow
Two men, one man and his dog
Went to mow a meadow
Three men went to mow
Went to mow a meadow
Three men, two men, one man and his dog
Went to mow a meadow
Write a Haskell function
song :: Int -> String
so that
song n
is the song when there are
n
men. Assume
n<10
.
To print the song, type for example
ghci> putStrLn (song 5)
The function
putStrLn
will be explained in the following chapter. I suggest starting with
song n = if n==0 then ""
else song (n-1) ++ "\n" ++ verse n
verse n = line1 n ++ line2 n ++ line3 n ++ line4 n
This defines
song
recursively
.
Answer to Exercise A
map double [1,4,4,3] | = [2,8,8,6] |
map (double . double) [1,4,4,3] | = [4,16,16,12] |
map double [] | = [] |
You will gather from this that
[]
denotes the empty list.
All the following equations hold:
sum . map double | = double . sum |
sum . map sum | = sum . concat |
sum . sort | = sum |
In fact, each of these three equations are consequences of the three simpler laws:
a*(x+y) | = a*x + a*y |
x+(y+z) | = (x+y)+z |
x+y | = y+x |
Of course, we don’t know yet how to
prove
that the equations hold. (By the way, to avoid fuss we will often use a typewriter
=
sign to denote the equality of two Haskell expressions written in typewriter font. But a mathematical = sign is used in equations such as sin 2
θ
= 2 sin
θ
cos
θ
.)
Answer to Exercise B
Both
sin theta^2
and
(sin theta)^2
are okay, but not
sin^2 theta
.
Here is the rendering of sin 2
θ
/2
π
in Haskell:
sin (2*theta) / (2*pi)
Note that
sin (2*theta) / 2
pi = (sin (2
theta) / 2) * pi
which is not what we want. The reason is that operators such as
/
and
*
at the same level of precedence associate to the left in expressions. More on this in the next chapter.
Answer to Exercise C
'H' | :: Char |
"H" | :: [Char] |
2001 | :: Integer |
"2001" | :: [Char] |
By the way,
'\'
is used as an
escape
character, so
'\n'
is the newline character, and
'\t'
is the tab character. Also,
'\\'
is the backslash character, and
"\\n"
is a list of two characters, a backslash and the letter
n
. As a consequence, the file path
C:\firefox\stuff
is written as the Haskell string
"C:\\firefox\\stuff"
.
[1,2,3] ++ [3,2,1] | = [1,2,3,3,2,1] |
"Hello" ++ " World!" | = "Hello World!" |
[1,2,3] ++ [] | = [1,2,3] |
"Hello" ++ "" ++"World!" | = "HelloWorld!" |
If you got the last two right, you will have appreciated that
[]
is an empty list of anything, but
""
is an empty list of characters.
Answer to Exercise D
The clue is in the phrase ‘converting each letter in each word to lowercase’. Converting each letter in a single word is expressed by
map toLower
, so the answer is
map (map toLower) . words
. That means the following equation holds:
words . map toLower = map (map toLower) . words
Answer to Exercise E
Numerical addition, list concatenation and functional composition are all associative. But of course, numerical subtraction isn’t. Nor is exponentiation. The identity element of addition is 0, the identity element of concatenation is the empty list, and the identity element of functional composition is the identity function:
id :: a -> a
id x = x
Answer to Exercise F
This exercise follows
Section 1.3
quite closely. One way of computing the function
anagrams n
is as follows: 1. Extract the words of length
n
, using a function