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.]

Merge Sort

Use your merge function to implement merge sort. That is, split the list you are given into two halves, recursively sort each half, and merge the halves.

*Main> mergeSort [1,9,3,2,7,6,4,8,5]
[1,2,3,4,5,6,7,8,9]
*Main> mergeSort [6,2,4,8,9,5,3,1,7,10]
[1,2,3,4,5,6,7,8,9,10]
*Main> mergeSort []
[]
*Main> mergeSort [4]
[4]
*Main> mergeSort "The quick brown fox jumps over the lazy dog."
"        .Tabcdeeefghhijklmnoooopqrrstuuvwxyz"

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.