CS 254 Lab 5: Botany and origami (trees and folds)

In this lab you will define several shorter functions on a couple of different types of trees, explore the use of folds on trees, and finally work on a couple of functions which use trees to improve the performance of database-like look-ups.

You may want to refer to the file Trees.hs developed in lecture as you work.

Shorter exercises

1. In lecture, in order to build a binary search tree (BST), we used the foldl function, rather than the more usual (and canonical) foldr. Answer the following questions (say in a text file):
   • if we had used foldr instead of foldl, what changes (if any) would we have had to make in the build function?
   • would we have built the same trees, in specific instances, if we built them using foldr rather than foldl?
   • would we have built valid binary search trees if we had built them using foldr rather than foldl?
2. Write the postord function we left out in lecture; it should return the postorder traversal of a BTree, where the left and right sub-trees are traversed first, and the node value "visited" last. (You may use either direct recursion or the binary tree fold.)
   For example, using the sample tree from lecture, you should have:

   Trees> postord sample
   "CDBGFJIKHEA"
   		

3. Write a fold function on general (rose) trees, of the following type:

   rfold :: (a -> [b] -> b) -> Rose a -> b

   Note that you will need to somehow propagate the recursive calls into the list of arguments.
4. Write each of the following functions for general trees (a.k.a. rose trees) in two different styles, using direct recursion and the rfold from above:

   • rsize :: Rose a -> Integer, to count the number of node values in a rose tree;
   • rheight :: Rose a -> Integer, to measure the height, or longest path from the root to a child (count the height of a leaf as one);
   • rsum :: Rose Integer -> Integer, to sum up all the (integer) node values in a rose tree;
   • rmap :: (a -> b) -> Rose a -> Rose b, to map a function across the node values in a rose tree
   • rpreord :: Rose a -> [a], to "flatten" a rose tree into a list of node values in preorder (i.e., node value first, then left and right sub-trees in that order);
   • rmirror :: Rose a -> Rose a, to return the "symmetric opposite" of a rose tree, as if it were mirrored down the middle.

   You should also write a test function that checks to make sure that the two versions of each of the functions defined above agree on the sample tree.

Look-up exercises

Recall the Haskell lookup function: it looks at a list of pairs of values, often called keys and items. You also give it a specific key value to look up in the list, and it returns (possibly!) an item: the item returned is an item which is paired with the key you gave. Note in particular that the look-up might fail to find a matching item: Haskell uses the Maybe in the result in order to allow for this possibility (so a successful item result will be "wrapped" up with a Just constructor). This look up itself requires that the key type supports an equality comparison, and so the type for lookup is:

lookup :: Eq a => a -> [(a,b)] -> Maybe b

Unfortunately, looking up a key in a long list of pairs can be relatively slow; fortunately, we know a way to speed this up, namely by using binary search trees (as discussed in lecture and used in the Trees.hs file.

So, let's define the following variations on lookup, using binary trees instead of lists to hold the "dictionary" of keys and items:

1. Define a function lookupbst :: a -> Tree (a,b) -> Maybe b will look up a key in a binary search tree of key value pairs, and return either Nothing or Just an item. NB: your function's type will actually have a qualifier on it reflecting the fact that the keys need to be ordered, since you will use comparisons on them; so it will look like: lookupbst :: Ord a => a -> Tree (a,b) -> Maybe b.
2. In order to test and use your function, you'll need to build appropriate argument search trees: define a function to insert a (key,value) pair into a tree, say insertbstpair, using the ordering defined on the keys to preserve the binary search tree aspect.

   (Note: remember to use the keys as the basis for the ordering, not the values; in other words, compare the left part of the input pair to the left part of the node value!)

   You can then use our old foldr trick to build a big sample tree from a list of inputs; for example:

   sample = foldr insertbstpair Tip mathlist
   
   mathlist = [("Erin",301), ("Colin",303), ("Gary",305),
               ("Inga",302), ("Peter",304), ("Mark",306), ("Josh",308)]

   
   (Note: office numbers may not be accurate ... especially after we move to Ford!)
3. What if there is more than one value associated with a given key? A nice way to handle situations like this might be to associate a list of items with each key, so now your type will be something like Tree (a,[b]). Make new definitions of search and insertion functions which use this idea. Specifically, your insert function would be of type insertkeylist :: (a,b) -> Tree (a,[b]) -> Tree (a,[b]) (i.e., you insert one item (b) with a key (a), but it either puts in a new node (for a completely new key) or adds to the list already there (for an existing key). Note that you won't need a Maybe in the result of your search function, since you can just use an empty list instead. (And remember to make your comparisons based on the left parts of the pairs, as above.)