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