TallCat

Logo

Webpage of the Compositional Systems and Methods group at TalTech.

Submission instructions

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

Deadline 23:00 09/04/2020

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"
    
    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)
    >