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. 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) group :: Eq a => [a] → [[a]]

Group adjacent identical elements into sublists. For example,

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

3. Cyclic List

Implelement the built-in function cycle that takes a list L and returns an infinite list consisting of L repeated over and over:

> take 10 (cycle "abc")
"abcabcabca"

4. Transpose

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

5. All Pairs

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

6. Mergesort

Write a function that sorts a list of values using a mergesort. Give your function an appropriate type using a type class constraing.

7. Collatz Sequence

Solve Project Euler's problem 14.