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).
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] ]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).
[[1,4,7],[2,5,8],[3,6,9]]
Your function should work for "non-square matrices" as well, as in the following example:
> transpose [ [1,2,3], [4,5,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.
[[1,4],[2,5],[3,6]]
data Tree a = Spread a [Tree a] deriving ShowDefine 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.
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:
For an example of breadth-first traversal, consider the following tree: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 = ([],[])
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.