DM509, Fall 2006, 2nd quarter - Weekly Note 3

Lecture November 21 (One hour only)

More examples of Haskel code, in particular folds.

Reading

Section 4.5 in Bird. Slide: examplesOfFold.hs. Additional (well commented) code example: matrix.hs. Section 5.5 in Bird is another good code example you may consider browsing (but it will not be curriculum).

Lecture November 23 (One hour only)

Trees. Handout of first project (the deadline is December 7, as stated, but if needed an extension to December 12 can be negotiated).

Reading

Sections 6.1 and 7.3.1 in Bird. First part of slides (trees.hs).

Lecture November 28 (Expected Contents)

More on trees. Discussion of first project. The value undef. Strict and non-strict functions. Proofs of properties of code.

Reading

Sections 6.2 and 7.4.1 in Bird. Chapters 1, 2 and 4 in Bird again, now with a focus on undef and on proofs. Second part of slides (trees.hs).

Exercises November 27

Exercises 4.5.6, 4.5.9, 4.5.10 in Bird.

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

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.

Exercises November 30

Make functions flatten, mapTree, and foldTree for the datatype BSTree a from the slides (trees.hs).

Make a function which implements a DFS traversal for the datatype BSTree a (Hint: if you go for at linear time solution, Section 7.3.2 may be inspirational (rose trees are defined in Section 6.4)).

Make a function which implements a BFS traversal for the datatype BSTree a (Hint: first consider making a function which takes a list of trees, and returns a (tuple consisting of) the list of roots and the list of subtrees of the roots).

Exercise 6.1.6 in Bird.

Exam of summer 2004 (pdf), exercise 3.