TDA 555
DIT 440
HT 2019

# Introduction to Functional Programming Exercises for Week 2

## Exercises for Week 2: Recursion and Datatypes

Here are some exercises designed to help you practice writing and reasoning about recursive definitions and datatypes.

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 GHCi accepts them.

### 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

 F0 = 1 F1 = 1 Fn+2 = Fn+1 + Fn

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: if you want to practise recursion, write `smallestFactor` by 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.

Now define

`numFactors n`

which computes the number of factors of n in the range 1..n.

### 6. (*) 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.

Optional extra: also define a function

`tomorrow :: Date -> Date`
that computes tomorrow's date for a given date.

### 7. (*) Replication

Define a function that replicates a given word n times
`repli :: Integer -> String -> String`
Example:
````repli 5 "ha"`
"hahahahaha"
```
As always, try to make the base case as small as possible!

Use the following function to concatenate two strings:

`(++) :: String -> String -> String`
Example:
````"flyg" ++ "plan"`
"flygplan"
```

### 8. (*) 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`).

### 9. 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`).