Exercises for Week 2: Recursion and Datatypes
Here are some exercises designed to help you practice writing and reasoning
about recursive definitions and datatypes.
Other helpful exercises can
be found in Chapters 3 and 4 of the book.
If you do not have time to do all these exercises, don't worry.
The exercises are intended to provide enough work to keep the most
experienced students busy. If you do all exercises marked with an (*) you have
probably understood this week's material.
Good luck!
1. (*) The Maximum Function
Complete the following function definition:
-- maxi x y returns the maximum of x and y
(We call this function maxi, because there is a standard function max which
does the same thing. Of course, you should not use it.)
Begin by writing a type signature for maxi, and a left hand side "equal to
undefined". Before you write the definition, think of at least one property that
you will use for testing your code.
You will need to consider two cases: what are they? Write the left hand sides,
and make sure Hugs accepts them.
Complete your definition and test it with QuickCheck.
2. Sum of squares.
Define a function which computes the sum of the squares of the numbers from 1 to n.
-- sumsq n returns 1*1 + 2*2 + ... + n*n
Hint: use recursion to compute sumsq n from sumsq (n-1); do not
use a formula (such as the one below) to compute this without recursion.
Some say that sumsq n is equal to n (n+1) (2n + 1) / 6. Use QuickCheck to
investigate whether this holds.
3. (*) The Towers of Hanoi
The Towers of Hanoi is an ancient puzzle, consisting of a collection of rings
of different sizes, and three posts mounted on a base. At the beginning all the
rings are on the left-most post as shown, and the goal is to move them all to
the rightmost post, by moving one ring at a time from one post to another. But,
at no time may a larger ring be placed on top of a smaller one!
Can you find a strategy for solving the puzzle based on recursion? That is,
if you already know how to move n-1 rings from one post to another, can you find
a way to move n rings?
If you try out your strategy, you will quickly discover that quite a large
number of moves are needed to solve the puzzle with, say, five rings. Can you
define a Haskell function
hanoi n
which computes the number of moves needed to move n rings from one post to
another using your strategy? How many moves would be needed to solve the puzzle
with ten rings? Legend has it that the original version of the puzzle has 32
rings, and is being solved at this very moment by Bhuddist monks in a monastery.
When the puzzle is complete, the world will end.
More difficult (only do this if you want a challenge): Now
suppose we add a fourth post to the puzzle. Can you think of a strategy
which makes use of the fourth post? Define a Haskell function to compute the
number of moves your new strategy needs to solve the puzzle. How many moves are
now required to solve the puzzle with ten rings? How much closer would the end
of the world be if the monks added a fourth post to their puzzle?
Can you explain this behaviour? Hint: what kind of recursion do your
two strategies use?
4. Fibonacci Numbers
The Fibonacci numbers are defined by
so the sequence of values begins 1, 1, 2, 3, 5, 8...
Write a recursive function
-- fib n computes the nth Fibonacci number
based on the mathematical definition above. Use it to compute the 10th, 15th,
20th, 25th, and 30th Fibonacci number. What do you notice? Can you explain this
behaviour?
More Difficult: There is a faster way to compute Fibonacci numbers.
Suppose we define a function fibAux which satisfies the property
fibAux i (fib n) (fib (n+1)) == fib (n+i)
Notice that this is not a definition, it is a property!
From this property can you see how we might redefine fib by
using fibAux? (Hint: try setting n to 0 in the property).
It is possible to derive a recursive definition of fibAux from this
property just using algebra: the two cases we want are
fibAux 0 a b = ...
fibAux i a b | i>0 = ...
See if you can use the property to figure out what the right hand sides
should be.
Use QuickCheck to test whether the new definition of fib (in terms of fibAux)
satisfies the property above.
Use the new version of fib to compute the 10th, 15th, 20th, 25th, and 30th
Fibonacci number. What do you notice?
Calculate fibAux 4 1 1 by hand. If you have programmed before, then observe
the way the values of i, a, and b change in successive recursive calls. Does it
remind you of anything?
5. Factors.
A prime number p has only two factors, 1 and p itself. A composite number has
more than two factors. Define a function
smallestFactor n
which returns the smallest factor of n larger than one. For example,
smallestFactor 14 == 2
smallestFactor 15 == 3
Before you program smallestFactor, write at least two QuickCheck
properties that it should satisfy. You will need functions for integer
division and remainder: investigate the standard functions
div
and mod
for this purpose.
Hint: write smallestFactor using an auxiliary function nextFactor k n which returns the
smallest factor of n larger than k. You can define smallestFactor using
nextFactor, and nextFactor by recursion. Write QuickCheck properties of
nextFactor before defining it also.
Now define
numFactors n
which computes the number of factors of n in the range 1..n.
For the following exercises, you can either use built-in Haskell lists, or
(if you want to) the type List we used in the lecture. These types are
basically the same, only the syntax is slightly different. For more about
the syntax of built-in Haskell lists, read the beginning of chapter 7 of
the book.
6. (*) Multiplying list elements
Define a function
multiply :: Num a => [a] -> a
which multiplies together all the elements of a list. (Think: what should its
value be for the empty list?). For example
multiply [1,2,3,4,5]
120
(This is actually a standard function, called product).
You may do this for the List datatype we saw in the lecture:
data List a = Empty | Add a (List a)
So, your function has the type:
multiply :: List Integer -> Integer
7. Avoiding Duplicates
In many situations, lists should not contain duplicate elements. For
example, a pack of cards should not contain the same card twice. Define a
function
duplicates :: Eq a => [a] -> Bool
which returns True
if its argument contains duplicate elements.
duplicates [1,2,3,4,5]
>
False
duplicates [1,2,3,2]
True
Hint: the standard function elem, which tests whether an element
occurs in a list, is helpful here.
One way to ensure a list contains no duplicates is to start with a
list that might contain duplicate elements, and remove them. Define a function
removeDuplicates :: Eq a => [a] -> [a]
which returns a list containing the same elements as its argument, but
without duplicates. Test it using the following property:
prop_duplicatesRemoved :: [Integer] -> Bool
prop_duplicatesRemoved xs = not (duplicates (removeDuplicates xs))
Does this property guarantee that removeDuplicates
behaves correctly? If not,
what is missing?
(removeDuplicates
is actually a standard function, called nub
).
8. Testing
Take the definition of rankBeats
from the lecture,
and sabotage it by
changing one of the False
results to True
,
or vice versa. Thorough testing of
rankBeats
ought to reveal the error. Your task is to define one or more
properties of rankBeats
, which are True for the correct definition, but which
enable you to reliably detect the error in the sabotaged definition using
QuickCheck.
(Note: Because QuickCheck chooses test data at random, it is always
possible that no error is found among the first 100 test cases. If you expect an
error, and none is found, just keep testing the same property. If it really is
False, then QuickCheck should eventually find a test case that fails).
9. (*) Defining Types
Define a data type Month
to represent months, and a function
daysInMonth :: Month -> Integer -> Integer
which computes the number of days in a month, given also the
year. (You can ignore leap centuries and the like: just assume that every
fourth year is a leap year).
Define a data type Date
, containing a year, month, and day, and
a function
validDate :: Date -> Bool
that returns True if the day in the date lies between 1 and the
number of days in the month.