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 (nonempty) 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
673 .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 preorder 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 keyvalue 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 keyvalue 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 keyvalue store of strings by first converting it to a rose tree, and drawing that. For example, if given the keyvalue 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 keyvalue 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)
>