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.
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.
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).
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.
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.)
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
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.)
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 (++)?
(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 4your program should return:
A wins in 4 out of 6 possible gamesAnd, given the sequence:
1 2 3your 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