Lab #5: Arboreal Origami (Trees and Folds)

Assigned:Wed 23 Feb 2005
Due: Wed 9 Mar 2005

These exercises are meant to give you a little practice working with tree data types and their folds.

1. We defined a function for the inorder traversal of a binary tree, producing a list, in lecture. Define functions for the pre-order and post-order traversals of a tree, using the following definition of a binary tree from lecture (you may use the fold function if you like, but you may also write your functions using straight recursion):

   data BTree a = Tip | Branch a (BTree a) (BTree a)  deriving Show
   
   fold t b  Tip           = t
   fold t b (Branch a l r) = b a (fold t b l) (fold t b r)

   Can you make your functions more efficient by using accumulating parameter techniques? (Try this as a second version, i.e., write simpler, non-accumulating versions first.)

   By way of example, here is the sample tree t from lecture and its preorder and postorder traversals:

   t = Branch 3 (Branch 1 Tip (Branch 2 Tip Tip))
                (Branch 5 (Branch 4 Tip Tip)
                          (Branch 7 Tip (Branch 9 Tip Tip)) )
   
   > preorder t
   [3,1,2,5,4,7,9]
   
   > postorder t
   [2,1,4,9,7,5,3]

   For the rest of the file from lecture, see this link.

2. Write a map function which will take a a function and a binary tree of arguments, and return a binary tree of corresponding results (i.e., apply the function to each node value in the binary tree).

   In other words, if we call this map function for binary trees mapbt, it should have the following type:

   mapbt :: (a -> b) -> BTree a -> BTree b

   Try writing the function both recursively and using the binary tree fold function from above.

   Demonstrate thet your function works by showing some examples of its use (at least one example should employ a function which returns a different type of argument than it takes).

3. Write a function mirror which will take a binary tree as an argument and return its mirror image, i.e., where left and right sub-trees have been interchanged at all levels.

   This time, try to use the fold function on trees to write your function from the get-go, i.e., don't write a regular recursive version first.

4. Binary trees are nice, but another useful kind of tree is one in which each node has an arbitrary number of children. We can represent these trees in a Haskell data type using a list of child trees, as follows:

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

   As warm-up exercises for the outline formatter below, write pre-order and post-ordertraversal functions for these sorts of trees, as well as a map. (You may write a fold to help you out with these, if you wish.)

5. Write a function which will convert a Tree into an outline format String for printing. In other words, the top node of the tree should be indented to a certain level, using tabs, and each of its children should appear below it, one per line, all of them indented one more tab than their parent. Of course, their children, descendant, should be formatted similarly.

   leaf x = Spread x []
   
   dogs = Spread "Dogs"
   		 [ Spread "Big dogs" [leaf "Dobermans", leaf "Sheep dogs",
   		 		Spread "Big red dogs" [leaf "Clifford"]],
   		   Spread "Small dogs" [leaf "Chihuahuas (sp?)", leaf "Poodles",
   		  		Spread "Small mean dogs" [leaf "Triump the comic insult dog"]]
   		 ]
   
   > outline dogs
   
   Dogs
   	Big dogs
   		Dobermans
   		Sheep dogs
   		Big red dogs
   			Clifford
   	Small dogs
   		Chihuahuas (sp?)
   		Poodles
   		Small mean dogs
   			Triumph the comic insult dog

6. A simple text index: given a short text (i.e., a long string), presumably with repeats in it, define a function which will print out a listing of all words which occur in the text, along with indices which represent where the word occurred (i.e., their "word number" within the text).

   This is a sort of poor man's book index, in the sense that if the string were longer (a whole book) and we used page numbers rather than word numbers, it would look like the index found in the back of most books.

   Here's an example text and its index listing:

   text = "this a text with some words in it and some of the words appear twice \
   		\and we are going to use only letters since it is hard to handle \
   		\things like commas so this text of ours will run to many words \
   		\and many of those words will be used twice such as words text in is it \
   		\and so on"
   
   a       2
   and     9, 16, 43, 59
   appear  14
   are     18
   as      53
   be      49
   commas  32
   going   19
   handle  29
   hard    27
   in      7, 56
   is      26, 57
   it      8, 25, 58
   letters 23
   like    31
   many    41, 44
   of      11, 36, 45
   on      61
   only    22
   ours    37
   run     39
   since   24
   so      33, 60
   some    5, 10
   such    52
   text    3, 35, 55
   the     12
   things  30
   this    1, 34
   those   46
   to      20, 28, 40
   twice   15, 51
   use     21
   used    50
   we      17
   will    38, 48
   with    4
   words   6, 13, 42, 47, 54

   How can you build such an index? Well, as a first step, get yourself a list of pairs of words and numbers: the words will be the words from the string, the numbers will be their indices (the zip function can be helpful here).

   Now you can define a variation on the binary search tree insertion algorithm given in class (again, see this link for the lecture code). In this version of BST insertion, however, you will insert a pair (word, number) into a tree which has (word, list of number) elements in it. When the inserted word is less or greater than the existing element word, you recurse on the left or right, as usual. But now, when the two words are equal, you just add the new number to the list.

   If you folding this function over your (word, number) pair list, you'll get a tree with pairs of words and number-lists. And if you inorder this tree, you'll get a list of pairs of words and number-lists. The only thing left is a less-than-enlightening formatting job, which I have done for you and supplied below, assuming your function has this type:

   indices :: String -> [(String, [Int])]

   Here is the code for the formatting function:

   fmt :: Show a => [(String,[a])] -> IO()
   fmt = putStrLn . concatMap line
         where line (word, ints) = concat ["\n", word, "\t", comma (map show ints)]
               comma = foldr1 (\i str -> i ++ ", " ++ str)

   (The final function should just compose together my formatter with your indices function.)

7. Given a "leaf tree" (i.e., one in which the internal nodes and leaves are of different types), write a function which will gather all the internal nodes and leaves of a tree into two lists:

   data LTRee a b = INode a (LTree a b) (LTree a b) | Leaf b  deriving Show
   
   sample = INode "who" (INode "do"  (Leaf 2) (Leaf 3))
                        (INode "foo" (Leaf 5) (INode "zoo" (Leaf 7) (Leaf 9)))
   
   lns :: LTree a b -> ([a],[b])
   
   > lns sample
   (["who", "do", "foo", "zoo"], [2,3,5,7,9])

   Can you write your function so that it uses only one pass through the tree? Can you do it more efficiently than using append (++)?

8. Sequence spinning game:

   (This question depends on the problem from the last lab for definitions of rotation and spinning for sequences.)

   Say that we wish to define a game around spinning sequences. We will need to add an element of choice at the very least, so we will say that two players alternate by choosing whether the rotation will be done to the right (as above) or to the left. Players A and B will alternate in making these choices (starting with A) until one of them manages to return to a previously seen state: this player is declared the winner. Assume for the moment that we wish only to analyze the probability of a win for each player, making no assumptions about the intelligence or foresight of the contestants. Write a program which will read in a sequence and print out the probability of a win for player A described as a ratio of whole numbers, namely the total number of wins for A, within the set of all possible game plays, versus the total number of possible plays.

   Note: if a player is confronted with a sequence beginning with 0, she may choose to rotate it either to the left or to the right, thus constituting two possible wins in the overall count.

   For example, given the sequence:

   1 2 3 4

   your program should return:

   A wins in 4 out of 6 possible games

   And, given the sequence:

   1 2 3

   your program should return:

   A wins in 2 out of 5 possible games

Please have answers to the above exercises ready for the lab session on Wednesday 9 March 2005