# TallCat Webpage of the Compositional Systems and Methods group at TalTech.

# Submission instructions

Email the following files to pawel@cs.ioc.ee:

• a single file called Solutions.idr, with all your solutions
• a file called statement.txt that says “I your name certify that the solutions submitted are my own”

# Functional Programming Assignment 2

## Part One

1. Consider the following data type
`````` 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)
``````
2. Write a function `foldRoseTree`, which implements the fold for `RoseTree`.

3. Write a function `mapRoseTree : (a -> b) -> RoseTree a -> RoseTree b`, which behaves analogously to the other map functions we have seen.

4. Write a function `flattenRose : RoseTree a -> List a` that returns a pre-order traversal of the given tree.

5. 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
``````
6. Write a function `sumRose : RoseTree Nat -> Nat` which sums the contents of the given tree.

7. Write a function `maxRose : Rose Nat -> Nat` which computes the largest entry in the given tree.

## Part Two

1. Recall that a binary search tree is a binary tree in which every value in the left subtree of a node is smaller than the value at that node, and similarly every value in the right subtree of a node is greater at that node. For this part of the assignment, we will the following datatype to represent binary search trees :
``````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)
``````
2. Write a function
``````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.

3. Write a function
``````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"
``````
4. Write a function
``````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.

5. Write a function `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"

. 10
The current state is:

"5 => banana"
|
+- "3 => orange"
|  |
|  '- "4 => mango"
|
'- "7 => apple"
|
'- "6 => papaya"

. 6
The current state is:

"5 => banana"
|
+- "3 => orange"
|  |
|  '- "4 => mango"
|
'- "7 => apple"

8 carrot
The current state is:
"5 => banana"
|
+- "3 => orange"
|  |
|  '- "4 => mango"
|
'- "7 => apple"
|
'- "8 => carrot"

2 cabbage
The current state is:
"5 => banana"
|
+- "3 => orange"
|  |
|  +- "2 => cabbage"
|  |
|  '- "4 => mango"
|
'- "7 => apple"
|
'- "8 => carrot"

6 potato
The current state is:

"5 => banana"
|
+- "3 => orange"
|  |
|  +- "2 => cabbage"
|  |
|  '- "4 => mango"
|
'- "7 => apple"
|
+- "6 => potato"
|
'- "8 => carrot"

7 pumpkin
The current state is:
"5 => banana"
|
+- "3 => orange"
|  |
|  +- "2 => cabbage"
|  |
|  '- "4 => mango"
|
'- "7 => pumpkin"
|
+- "6 => potato"
|
'- "8 => carrot"