# Exercise 5

For this exercise, put all of your function definitions in a file `exer5.hs`

. You will also create a text file, `exer5.txt`

. **You must include an appropriate type declaration** (`::`

) for each function you define in your `exer5.hs`

.

## Built-In Functions

There are many useful functions that come with the language, but most of them are actually fairly simple to implement recursively. Let's prove that by doing a few.

- Write a recursive function
`myIterate`

that behaves identically to the built-in`iterate`

. - Write a recursive function
`myTakeWhile`

that behaves identically to the built-in`takeWhile`

.

## Pascal's Triangle

Write a recursive function `pascal`

to generate the *n*th row of Pascal's triangle. Forget anything you might remember about combinatorics: we'll calculate the values in each row by recursively adding elements from the previous row.

```
*Main> pascal 0
[1]
*Main> pascal 1
[1,1]
*Main> pascal 2
[1,2,1]
*Main> pascal 3
[1,3,3,1]
*Main> pascal 12
[1,12,66,220,495,792,924,792,495,220,66,12,1]
```

Hint: given the previous row of Pascal's triangle `prev`

, consider the result of

```
zip prev (tail prev)
```

## Pointfree Addition

Use the `curry`

or `uncurry`

functions to give a pointfree (or tacit) definition of a function `addPair`

(i.e. do not mention any arguments: define it like `addPair = …`

).

```
*Main> addPair (2,3)
5
*Main> addPair (100, 3+4)
107
```

## Pointfree Filtering

Use partial function application to give a **pointfree** definition of a function `withoutZeros`

that removes any zeros from a list of numbers.

```
*Main> withoutZeros [1,2,0,3,4,0,5,6,0]
[1,2,3,4,5,6]
*Main> withoutZeros [0.0, 0.1, 0.2, 0.3]
[0.1,0.2,0.3]
```

Hint: you'll need to get the typeclasses right for the arguments. The list must have elements that are both comparable for equality (`Eq`

, since you want to use `/=`

on them) and are numeric (`Num`

, since you want to compare to zero).

## Exploring Fibonacci

The Fibonacci sequence is an infinite sequence of values formed by using the identity \(F_n = F_{n-1} + F_{n-2}\). Write a function `fib`

that calculates the given value in the sequence **using this identity**. (Like with the Pascal's Triangle example: forget anything you might know about a closed-form solution to calculate these values. Implement the naïve recursive algorithm.)

```
*Main> fib 0
0
*Main> fib 1
1
*Main> fib 2
1
*Main> fib 3
2
*Main> fib 10
55
*Main> fib 20
6765
```

Also define the infinite sequence of Fibonacci numbers like this:

```
fibs = map fib [0..]
```

## Fibonacci Speed

Try evaluating `fib 33`

with your function defined above. It should take a few seconds to evaluate, depending on your system. (If it doesn't take a noticeable amount of time, try `fib 35`

. If you happen to be using Hugs, try starting with 25.) Try evaluating `fib 45`

. (Control-C will stop a long calculation.)

In your `exer5.txt`

file, answer this question: Why do you think the `fib`

function you have defined takes so long to do seemingly simple calculations?

## Something Else

Add this definition to your `exer5.hs`

:

```
things :: [Integer]
things = 0 : 1 : zipWith (+) things (tail things)
```

Have a look at the first values of this infinite list (with `take`

). In your `exer5.txt`

file, answer these questions…

Describe the values in the `things`

list. [Hint: compare with the previous questions.]

Describe how the values in `things`

are calculated, using what you know about lazy evaluation.

Evaluate `things!!33`

and `things!!45`

. Why is this calculation so much faster than calculating the values in the list `fibs`

?

## Submitting

Submit your files through CourSys for Exercise 5.