Week 10: Exercises

1. Valid Search Tree

Consider this definition of a binary tree:

data Tree a = Nil | Node (Tree a) a (Tree a)

Write a function is_search_tree that determines whether a binary tree is a valid binary search tree:

is_search_tree :: Ord a => Tree a -> Bool

Assume that duplicate values are not allowed in the tree.

2. Tree Fold

1. Write a function tree_foldr that performs a right fold of a function over the values in a binary tree:

   tree_foldr :: (b -> a -> a) -> a -> Tree b -> a

2. Use tree_foldr to write functions that

   • add all the values in a binary tree of numbers;

   • generate a list containing all the values in a binary tree

3. Tree Insertion

1. Write a function that can insert a value into a binary search tree. Choose an appropriate type for your function.

2. Using the function you wrote in part (a), write a function that inserts all values in a given list into a binary search tree.

4. Balanced Tree

We will say that a binary tree is balanced if for every node in the tree, the left and right subtrees differ in height by at most 1. Write a function that takes a binary tree and returns True iff it is balanced.

5. Prefix Expressions

We can use this an algebraic data type to represent an arithmetic expression:

data Expr = Const Int | Var String |
            Add Expr Expr | Sub Expr Expr | Mul Expr Expr

a) Write a function parse :: String -> Expr that can parse an expression written in prefix notation, such as

* + x y - x y
* z - z 2
14
+ 0 + 1 + 2 3

You may assume that (as in the examples above) all input tokens are separated by spaces.

b) Write a function eval :: [(String, Int)] -> Expr -> Int that evaluates an expression. The first argument to the function is an environment, i.e. an association list that maps variables to their values.

6. Simplifying Expressions

Write a function simplify :: Expr -> Expr that simplifies an expression by combining constants wherever possible, and by eliminating additions/subtractions with 0 or multiplications with 1.

For example, 0 + (x + (2 + 3)) should simplify to x + 5.