Week 8: Notes

Here are the solutions to the exercises we solved in the Thursday tutorial.

Pythagorean Triples

1. Write a function that takes an integer N and returns a list of all integer triples (a, b, c) with a < b < c ≤ N such that a² + b² = c². Your function should run in time O(N³).

triples1 n =
  [ (a, b, c) | c <- [3 .. n], b <- [1 .. c - 1], a <- [ 1 .. b - 1],
                a ^ 2 + b ^ 2 == c ^ 2 ]

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

-- Return the square root of n if it is a perfect square, otherwise -1.
intSqrt n = search 0 (n + 1) n
  where search lo hi n =
          if hi == lo + 1 then -1 else
            let mid = (lo + hi) `div` 2 in
              if mid * mid == n then mid
              else if mid * mid < n then search mid hi n
                                    else search lo mid n

triples2 n =
  [ (a, b, c) | b <- [2 .. n], a <- [1 .. b - 1],
                let c = intSqrt (a ^ 2 + b ^ 2), c /= -1, c <= n ]

Matrix Addition

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

addVec v w = [ a + b | (a, b) <- v `zip` w ]

addMat m n = [ addVec v w | (v, w) <- m `zip` n ]

All Pairs

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

allPairs = [ (a, s - a) | s <- [2 .. ], a <- [1 .. s - 1] ]