Webpage of the Compositional Systems and Methods group at TalTech.
Email the following files to pawel@cs.ioc.ee:
Deadline 23:00 09/04/2020
data RoseTree : Type -> Type where
Rose : a -> List (RoseTree a) -> RoseTree a
which we understand as the type of (non-empty) arbitrarily branching trees. The idea being that (Rose x rs)
is the tree with root x
and children rs
. For example
exampleTree : RoseTree Nat
exampleTree = Rose 6 [Rose 7 [Rose 4 [], Rose 3 [], Rose 8 [ Rose 9 [], Rose 10 []]]]
represents the tree
.--4
6--7-|--3 .-9
'--8-|
'-10
we could also draw this tree as
6
|
'- 7
|
+- 4
|
+- 3
|
'- 8
|
+- 9
|
'- 10
and it is this latter representation we will use for the remainder of the assignment. You may use the following implementation of show
for RoseTree
, which produces drawings of trees in this style, to help you with the assignment. It is often difficult to tell which tree a given expression represents witout drawing it!
draw : RoseTree String -> List String
draw (Rose x ts') = lines x ++ drawSubTrees ts'
where
shift : String -> String -> List String -> List String
shift first other more =
zipWith (++) (first :: (replicate (length more) other)) more
drawSubTrees : List (RoseTree String) -> List String
drawSubTrees [] = []
drawSubTrees [t] =
"|" :: shift "'- " " " (draw t)
drawSubTrees (t :: ts) =
"|" :: shift "+- " "| " (draw t) ++ drawSubTrees ts
Show a => Show (RoseTree a) where
show t = unlines (draw (stringify t))
where
stringify : RoseTree a -> RoseTree String
stringify (Rose x xs) = Rose (show x) (map stringify xs)
Write a function foldRoseTree
, which implements the fold for RoseTree
.
Write a function mapRoseTree : (a -> b) -> RoseTree a -> RoseTree b
, which behaves analogously to the other map functions we have seen.
Write a function flattenRose : RoseTree a -> List a
that returns a pre-order traversal of the given tree.
Write a function reverseRose : RoseTree a -> RoseTree a
that reverses the given tree. For example reverseRose exampleTree
is
6
|
'- 7
|
+- 8
| |
| +- 10
| |
| '- 9
|
+- 3
|
'- 4
Write a function sumRose : RoseTree Nat -> Nat
which sums the contents of the given tree.
maxRose : Rose Nat -> Nat
which computes the largest entry in the given tree.data Tree : Type -> Type where
Leaf : Tree a
Node : Tree a -> a -> Tree a -> Tree a
One way to use binary search trees is as a key-value store. The idea is to maintain a tree of pairs (Nat,a)
for some type a
where the first component of the pair is used to locate the second component in the tree.
KVStore : Type -> Type
KVStore a = Tree (Nat,a)
insert : (Nat,a) -> KVStore a -> KVStore a
that inserts the first argument into the key-value store, returning the result. Be sure that the result of an insertion is still a binary search tree.
drawStore : KVStore String -> IO ()
that draws a key-value store of strings by first converting it to a rose tree, and drawing that. For example, if given the key-value store
exampleStore : KVStore String
exampleStore = insert (7, "apple") $
insert (6 , "papaya") $
insert (4 , "mango") $
insert (3 , "orange") $
insert (7 , "cabbage") $
insert (10 , "pineapple") $
insert (5 , "banana") Leaf
the output of drawStore exampleStore
should look more or less like
"5 => banana"
|
+- "3 => orange"
| |
| '- "4 => mango"
|
'- "10 => pineapple"
|
'- "7 => apple"
|
'- "6 => papaya"
delete : Nat -> KVStore String -> KVStore String
that deletes the node with the given key (in any) from the store , returning the result. Again, be sure that the result of a deletion remains a binary search tree.
edit : KVStore String -> IO (KVStore String)
that allows you to interactively edit a key-value store by inserting and deleting things, printing the current tree at after each operation. For example:
> :exec (edit exampleStore)
The current state is:
"5 => banana"
|
+- "3 => orange"
| |
| '- "4 => mango"
|
'- "10 => pineapple"
|
'- "7 => apple"
|
'- "6 => papaya"
Please enter a command:
. 10
The current state is:
"5 => banana"
|
+- "3 => orange"
| |
| '- "4 => mango"
|
'- "7 => apple"
|
'- "6 => papaya"
Please enter a command:
. 6
The current state is:
"5 => banana"
|
+- "3 => orange"
| |
| '- "4 => mango"
|
'- "7 => apple"
Please enter a command:
8 carrot
The current state is:
"5 => banana"
|
+- "3 => orange"
| |
| '- "4 => mango"
|
'- "7 => apple"
|
'- "8 => carrot"
Please enter a command:
2 cabbage
The current state is:
"5 => banana"
|
+- "3 => orange"
| |
| +- "2 => cabbage"
| |
| '- "4 => mango"
|
'- "7 => apple"
|
'- "8 => carrot"
Please enter a command:
6 potato
The current state is:
"5 => banana"
|
+- "3 => orange"
| |
| +- "2 => cabbage"
| |
| '- "4 => mango"
|
'- "7 => apple"
|
+- "6 => potato"
|
'- "8 => carrot"
Please enter a command:
7 pumpkin
The current state is:
"5 => banana"
|
+- "3 => orange"
| |
| +- "2 => cabbage"
| |
| '- "4 => mango"
|
'- "7 => pumpkin"
|
+- "6 => potato"
|
'- "8 => carrot"
Please enter a command:
done (returns final tree)
>