DM22, Spring 2007 - Weekly Note 5

Lecture February 26

More on fold functions.

Reading

Section 4.5 in Bird (again). You may consider browsing Chapter 5 for more examples of Haskell programs.

Lecture March 5 (Expected Contents)

Trees. Accumulators and tupling.

Reading

Sections 6.1-2 and 7.3-4 in Bird.

Exercises March 7

Exercises 4.5.6, 4.5.9, 4.5.10, 4.5.12 (the answer is in the standard Prelude - try not to look before finishing your own solution) in Bird.

Exam of winther 2007 (pdf), exercise 1.

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.