# Exercise 3

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

.

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

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

.

## Merging

Write a recursive function `merge`

that takes two already-sorted lists, and combines them into a single sorted list.

```
*Main> merge [2,4,6,8] [1,3,5,7]
[1,2,3,4,5,6,7,8]
*Main> merge [1,2,3,4] [5,6,7,8,9,10]
[1,2,3,4,5,6,7,8,9,10]
*Main> merge [4,5,7,8] [1,2,3,6,9]
[1,2,3,4,5,6,7,8,9]
*Main> merge "aeguz" "ceptw"
"aceegptuwz"
```

[Your `merge`

function should take linear (\(O(n)\)) time. i.e. you shouldn't use a sort function as part of your implementation.]

## Tail Recursive Hailstone

Have a look at your `hailLen`

function from exercise 2. Rewrite the function so it gives the same results in all cases, but is **tail recursive**. (That is, you should return the result of any recursive call immediately, not use it as part of some larger expression.)

You will need to introduce an “accumulator” argument to do this properly. The way to hide this from the outside world is by defining the recursive part in a `where`

clause:

```
hailLen n = hailTail ⏹ n
where
hailTail a ⏹ = ⏹
hailTail a ⏹ = hailTail ⏹ ⏹
```

You can also move `hailTail`

out of the `where`

to test is separately: it may be better to start that way and hide it once you're confident that it's correct.

(If you did the exercise 2 function tail-recursively, include it here and write a non-tail-recursive version now.)

## Factorial

Write a recursive function `fact`

that takes one argument calculates its factorial. That is,

```
*Main> fact 0
1
*Main> fact 5
120
*Main> fact 10
3628800
```

### With a fold

Write a function `fact'`

that gives exactly the same results as fact, but is **not recursive** and is implemented with `foldl`

.

## Haskell Library and Dates

It's time to expand our knowledge of the Haskell standard library. For the rest of the exercise, we will use some of the date/time modules, which can be imported like this: (A Haskell import must be before any function definitions in the file.)

```
import Data.Time.Calendar
import Data.Time.Calendar.OrdinalDate
```

Create a function `daysInYear`

that returns a list of all days in a given year: each should be a `Day`

type. Hint: use the `fromGregorian`

function and…

```
daysInYear :: Integer -> [Day]
daysInYear y = [⏹..⏹]
where jan1 = ⏹
dec31 = ⏹
```

(It turns out that the `..`

notation can be used on any type that is in the `Enum`

class, not just integers.)

Create a function `isFriday`

that takes an argument of type `Day`

and returns `True`

if that day is a Friday (and `False`

otherwise).

```
*Main> isFriday (fromGregorian 2018 5 17)
False
*Main> isFriday (fromGregorian 2018 5 18)
True
*Main> filter isFriday (daysInYear 2018)
[2018-01-05,2018-01-12,2018-01-19,…]
```

The mondayStartWeek function (or sundayStartWeek function) calculates the day of the week. See also the `snd`

function.

I also like days that are prime numbers. For example, Friday the 13th: 13 is a prime number, so that's a good day. Write a function `isPrimeDay`

that takes a `Day`

as an argument and returns `True`

if they day part is prime.

```
*Main> isPrimeDay (fromGregorian 2018 5 13)
True
*Main> isPrimeDay (fromGregorian 2018 5 14)
False
*Main> isPrimeDay (fromGregorian 2018 6 23)
True
```

You can use the `divisors`

function from exercise 2 to help you get there.

At some point, you'll probably find that you used `toGregorian`

and have a triple (tuple with three values) that contains a year, month, and day. This function does something useful when given such a triple as an argument:

```
getDay (y,m,d) = d
```

Use the functions you have created to define a `primeFridays`

function that returns a list of all prime Fridays in a year.

```
*Main> primeFridays 2018
[2018-01-05,2018-01-19,2018-02-02,2018-02-23,2018-03-02,…]
```

## Submitting

Submit your files through CourSys for Exercise 3.