Week 8: Exercises

1. Function Types

What are the types of these functions?

1. triple x = 3 * x

2. even x = (x `mod` 2 == 0)

3. palindrome xs = (reverse xs == xs)

4. zip [] [] = []
zip (x : xs) (y : ys) = (x, y) : (zip xs ys)

5. f x = f x

2. Or

Which of these functions is equivalent to the built-in operator || ?

1. or _ True = True
or True _ = True
or _ _ = False

2. or True False = True
or True True = True
or False True = True
or False False = False

3. or a b = b || a

3. Prime Factors

Write a function primeFactors that takes an integer and returns a list of its prime factors in ascending order:

> primeFactors 60
[2, 2, 3, 5]

4. Pythagorean Triples

1. Write a function that takes an integer N and returns a list of all integer triples (a, b, c) with 0 < a < b < c ≤ N such that a² + b² = c²:

   > triples 15
[(3,4,5),(6,8,10),(5,12,13),(9,12,15)]

   Your function should run in time O(N³).

2. Make your function more efficient so that it runs in O(N² log N). Do not use any floating-point numbers.

5. Matrix Addition

Write a function that adds two matrices represented as lists of lists.

6. Matrix Transposition

Write a function that transposes a matrix represtented as a list of lists.

7. Insertion Sort

Write a function that sorts a list using an insertion sort.

8. Merge Sort

Write a function that sorts a list using a merge sort.

9. All Pairs

Construct an infinite list allPairs that contains all pairs of positive integers. Every pair must appear exactly once in the list.

10. Permutations

Write a function that returns a list of all permutations of a given list.