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

Primes and Divisors

The following functions should calculate the divisors of a number (excluding 1 and the number itself) and the list of prime numbers up to the argument. Copy the partial functions and fill in the blanks (⏹; replacement may be of any length) so the functions work.

divisors :: Int -> [Int]
divisors n = [⏹ | i <- [2..(⏹ `div` 2)], ⏹ `mod` ⏹ == 0]
primes :: Int -> [Int]
primes n = [i | i <- [⏹], divisors i == ⏹]

When you're done, the functions should work like this:

*Main> divisors 30
[2,3,5,6,10,15]
*Main> divisors 64
[2,4,8,16,32]
*Main> divisors 127
[]
*Main> primes 7
[2,3,5,7]
*Main> primes 100
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]

Pythagorean Triples

Write a function pythagorean that finds Pythagorean triples (values \(a\), \(b\), \(c\) all integers greater than 0, where \(a^2 + b^2 = c^2\)).

The function should take one argument which is the maximum value for \(c\). It should return a list of tuples containing the \(a\), \(b\), \(c\) values. The result should contain no duplicates: not both of (4,3,5) and (3,4,5) (but either one is fine, as is any order of the triples within the list).

*Main> pythagorean 10
[(3,4,5),(6,8,10)]
*Main> pythagorean 30
[(3,4,5),(6,8,10),(5,12,13),(9,12,15),(8,15,17),(12,16,20),(15,20,25),(7,24,25),(10,24,26),(20,21,29),(18,24,30)]

Your function should be implemented with a list comprehension. Include this type declaration before your function definition:

pythagorean :: Int -> [(Int, Int, Int)]

Joining Strings

Create a recursive function join that takes a string (the separator) and a list of strings. The strings (from the list) should be joined into a single string by putting the separator between them. For example:

*Main> join ", " ["one","two","three"]
"one, two, three"
*Main> join "+" ["1","2","3"]
"1+2+3"
*Main> join "X" ["abc"]
"abc"
*Main> join "X" []
""

You must do this with pattern matching on the arguments.

Factorial with a fold

Write a function fact' that gives exactly the same results as fact from last week, but is not recursive and is implemented with foldl.

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

Tail Recursive Hailstone

Have a look at your hailLen function from exercise 1. 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. You can re-use your hailstone function from last week for this.

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

Submitting

Submit your files through CourSys for Exercise 2.