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
    > postorder t
    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
    	Big dogs
    		Sheep dogs
    		Big red dogs
    	Small dogs
    		Chihuahuas (sp?)
    		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