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:
-
Make a function
multMV :: Matrix -> Vector -> Vector
which takes a matrix A and a vector x , and computes
the product A x .
-
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.
- 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.
-
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.
-
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 Int s do not support the / operator (as
Float s 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 .
Maintained by Rolf Fagerberg
(rolf@imada.sdu.dk)
|
|