DM22, Spring 2006 - Weekly Note 5

Lecture March 7

More examples of actual Haskell programming. The undefined value. Strict and non-strict functions. Proofs of properties of code.

Reading

Slides: matrix.hs

Chapters 1 and 2 again, now with a focus on the undefined value, and on proofs.

Lecture March 14 (Expected contents)

More examples of proofs of properties of code. Trees.

Reading

Chapter 4 again, now with a focus on the undefined value, and on proofs. Start on Chapter 6.

Exercises March 15

Any remaining exercises from last weekly note.

Exam of summer 2002 (pdf), exercise 4. Note: the types stated are not entirely correct - they should start with the context Num a =>, i.e. it is required that the type variable a only ranges over types in the class Num (else addition and multiplication are not necessarily available on the type).

Exercises 1.3.2, 2.4.1, 2.5.1, and (optional) 2.5.2 (hint: consider the left- and the right-hand sides applied to the values Left x and Right x, and use the identities at the top of page 47).

The following extensions of the example code matrix.hs on matrix operations:

1. Make a function

   multMV :: Matrix -> Vector -> Vector
   

   which takes a matrix A and a vector x, and computes the product A x.

2. Make functions

   lengthV :: Vector -> Entry
   normalizeV :: Vector -> Vector
   

   where lengthV computes the length of a vector, and normalizeV scales a vector so it gets length one. Recall that the length of a vector is the squareroot of its vector product with itself.

3. An eigenvector of a square matrix A is a vector x for which A x = l x for some scalar value l (called the corresponding eigenvalue). For almost any vector x, the sequence n(A x), n(A n(A x)), n(A n(A n(A x))),..., where n stands for normalization of a vector, will converge to an eigenvector of A (namely the eigenvector with the largest eigenvalue, called the principal eigenvector/eigenvalue). In other words, the method simply consists of repeated multiplication of A, while keeping the vectors produced normalized (i.e. of length one).

   Make a function

   eigenlistM :: Matrix -> Vector -> [Vector]
   

   which, given a vector A and some initial vector x, produces the (infinite) sequence above. Hint: consider the function iterate from the standard library.

4. Make a function

   eigenM :: Matrix -> Vector -> Float -> Vector
   

   which given a vector A, some initial vector x, and some small threshold epsilon (e.g. epsilon = 1.0e-6), returns the first vector in the sequence where the difference from the previous one is less than epsilon for all positions in the vector. In other words, make a function which can find an approximation to the principal eigenvector. Hint: consider the function dropWhile from the standard library.

5. Using the result from the previous exercise, make a function which finds an approximation to the principal eigenvalue (given some inital vector x).

   One hint: if you consider finding the average of a list of Floats, note that length from the standard library returns the type Int, and that Ints do not support the / operator (as Floats do). One solution is to use the built-in function fromIntegral, which will take any type in the class Integral (including the type Int) to any type in the class Num (including Float). So a / fromIntegral b will work for a in Float and b in Int.