DM22, Spring 2007 - Weekly Note 6

Advertisement: The next Matalogi-party will take place Friday, April 20. There will be live band, good food, and of course nice company. Sign up at the departmental office.

Lecture March 5

Accumulators. Trees.

Reading

Sections 6.1, 7.3.1, and 7.3.3 in Bird. Slides (trees.hs)

Lecture March 12 Expected Contents)

More on Trees. Tupling. Modules. Handout of first project.

Reading

Sections 6.2, 7.4.1-2, 7.4.4, and 8.2 in Bird. Slides (trees.hs).

Exercises March 14

Exercise 7.3.1 in Bird.

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. The function should return a list containing the elements of the tree in the order they will be met during a DFS traversal. (Hint: if you go for at linear time solution, consider using an accumulator).

Make a function which implements a BFS traversal for the datatype BSTree a. The function should return a list containing the elements of the tree in the order they will be met during a BFS traversal. (Hint: first consider making a function which takes a list of trees, and returns a (a tuple consisting of) the list of roots and the list of subtrees of the roots).

Exam of summer 2002 (pdf), exercise 4.

Exam of summer 2004 (pdf), exercise 3.