Not logged in. Login

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

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

Updated Wed April 07 2021, 12:59 by ggbaker.