Not logged in. Login

Exercise 2

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

Hailstone Length

Write a recursive function hailLen (using pattern matching) that calculates the length of the hailstone sequence starting at the argument. (i.e. the number of values in the sequence before it gets to one)

*Main> hailLen 11
14
*Main> hailLen 27
111
*Main> hailLen 686901248
270
*Main> hailLen 1
0

You should not construct a list and calculate its length. Use your function hailstone from last week to do this.

Aside: it is not known whether or not this function halts for all inputs since it has not been proven that every hailstone sequence gets to one. But the sequence does terminate for all values up to $$2^{64}$$, so that should get us through this exercise.

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]

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.

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

Submitting

Submit your files through CourSys for Exercise 2.

Updated Sat Aug. 25 2018, 11:27 by ggbaker.