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

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.

Updated Fri Sept. 14 2018, 08:57 by ggbaker.