Week 7: 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. f x = f x

2. List Functions

Write these functions (which are all built into the standard library):

a) isPrefixOf :: Eq a => [a] → [a] → Bool

Take two lists and return true if the first list is a prefix of the second.

b) isInfixOf :: Eq a => [a] → [a] → Bool

Take two lists and return true if the first list is contained anywhere within the second.

c) elemIndex :: Eq a => a → [a] → Maybe Int

Return the index of the first element in the given list that is equal to the query element, or Nothing if there is no such element. Elements are indexed starting from 0.

d) group :: Eq a => [a] → [[a]]

Group adjacent identical elements into sublists. For example,

group "Mississippi" == ["M","i","ss","i","ss","i","pp","i"]

3. Prime

Write a function that determines whether an integer is prime.

4. All Primes

Construct an infinite list containing all prime numbers.

5. Vector Sum

Write a function add_vec that adds two vectors represented as lists. Give your function the most general possible type.

6. Dot Product

Write a function dot that computes the dot product of two vectors represented as lists.

7. Matrix Addition

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

8. Sorting

Write a function that sorts a list of values using one of the following algorithms: insertion sort; selection sort; merge sort; quicksort.

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. Infinite Diagonal Matrix

Construct an infinite diagonal matrix as an infinite list of lists:

[[1, 0, 0, 0, ...],
 [0, 1, 0, 0, ...],
 [0, 0, 1, 0, ...],
 .
 .
 .
 ]

11. Permutations

Write a function permutations :: [a] -> [[a]] that returns a list of all permutations of a given list. Do not assume that the type a implements Eq.

12. Pythagorean Triples

Write a function triples that takes an integer N and returns a list of integer triples (a, b, c) with 0 < a < b < c ≤ N such that a² + b² = c². If two triples are multiples of each other (e.g. (3, 4, 5) and (6, 8, 10)), only the smaller of them (e.g. (3, 4, 5)) should appear in the list.

> triples 15
[(3,4,5),(5,12,13)]