Lab #6: Some extra, short exercises (extra-short?)

Assigned: Wed 16 Mar 2005 um, actually not
Due: Wed 16 Mar 2005

These exercises are meant to give you a little extra practice working with trees and lists. They are meant as a supplement to the last lab (#5) and are part of a "package deal" in the sense that all the exercises, labs 5 & 6, will be due next Tuesday in lecture (so some extra time has effectively been granted for Lab 5).

1. As we have seen earlier this semester, the zip, and zipWith functions can be very useful. In combination, zip and unzip allow us to transform a pair of lists into a list of pairs and back again (note that they are not quite full inverses; why?). In many situations, it is nice to have the same functionality, but with different combinations of structures, for example, a list of lists rather than a list of pairs.

   Write a function transpose which will take a list of lists and exchange the two levels of structure. I.e., it should return a list of lists, but now with the first list consisting of the heads of all the original lists, the secnd list their second elements, etc.

   > transpose [ [1,2,3], [4,5,6], [7,8,9] ]
   [[1,4,7],[2,5,8],[3,6,9]]

   Note the reason for the name transpose: if you view the list of lists as a representation of a matrix by rows (resp. columns), then the result is a representation by columns (resp. rows).

   Your function should work for "non-square matrices" as well, as in the following example:

   > transpose [ [1,2,3], [4,5,6] ]
   [[1,4],[2,5],[3,6]]

   If possible, see if you can get your function to trim longer lists to fit shorter ones, a la zip. This is a bit trickier than for nice, "rectangular" matrices.

2. Assume given the same definition for multi-branch trees as in the last lab lecture; that is:

   data Tree a = Spread a [Tree a] deriving Show

   Define a zipt function which zips two trees together into a single tree of pairs.

   zipt :: Tree a -> Tree b -> Tree (a,b)

   If the two original trees have the same shape, then the resulting tree should also have this shape. On the other hand, if either tree is "short" in some respect (i.e., fewer children at a specific sub-node) , the result should be trimmed to the "shorter" of the trees.

3. A nice exercise in combining data structures is to implement breadth-first (or level-order) traversal of a tree using a queue. That is, write a function which will take a tre and return a list of its elements, but in such an order that the root comes first, then all the elements one level below the root (and in original left-to-right order), then all the "grand-children", etc.

   As I'm sure you learned in Data Structures class, breadth-first traversal is different from depth-first traversal in that it does not lend itself quite so easily to a straight recursion. (In Haskell, we have seen how to do a depth-first or "flatten" function using folds.) In fact, we can see a deep connection between the two by noticing that both kinds of traversal can be accomplished with one general algorithm, but by using a different auxiliary data structure in the two cases, namely a stack for depth-first traversal and a queue for breadth-first traversal. (If we use recursion to do a depth-first traversal, the "stack" is the run-time system's stack of pendign recursive function calls.)

   The idea here is to enqueue the root node to start with, and then to successively dequeue nodes, one at a time, adding their elements to the list of results and then enqueuing their children, until the queue becomes empty.

   Here is a quick (but tricky!) implementation of queues you can use in Haskell:

   type Queue a = ([a],[a])
   
   enq :: a -> Queue a -> Queue a
   enq x (a,b) = (x:a,b)
   
   deq :: Queue a -> (a, Queue a)
   deq ([],[]) = error "empty queue"
   deq (a,x:b) = (x,(a,b))
   deq (a,[])  = deq ([], reverse a)
   
   empty :: Queue a
   empty = ([],[])

   For an example of breadth-first traversal, consider the following tree:

   test = Spread 0 [ Spread 1 [leaf 4, leaf 5],
                     leaf 2, 
                     Spread 3 [leaf 6, leaf 7, leaf 8]]

   (here I have defined a convenient helper function leaf so that leaf x = Spread x []; this isn't a separate constructor for the data type, it's just a handy way of abbreviating an oft-occurring pattern of code).

   You should have this breadth-first traversal:

   > breadth test
   [0,1,2,3,4,5,6,7,8]

Please have answers to the above exercises ready for the next lab session on Wednesday 16 March.