Week 7: Exercises

Solve the following problems in Haskell.

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. 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 a2 + b2 = c2:

    > triples 15

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

    Your function should run in time O(N3).

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

4. Insertion Sort

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

5. Merge Sort

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

6. Infinite Ints

Construct a list ints of integers from 1 to ∞, without using the built-in range operator (i.e. [1 .. ]).

7. 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"

8. All Pairs

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