Week 11: 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 isSearchTree that determines whether a binary tree is a valid binary search tree:

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

Assume that duplicate values are not allowed in the tree.

2. Tree Fold

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

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

2. Use treeFoldr 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. Infinite Tree

Construct an infinite binary tree of type Tree Integer that looks like this:

6. Lists and Integers

1. Suppose that lists were not built into Haskell. How you could you define them using an algebraic data type?

2. Suppose that integers were not built into Haskell. How you could you define them using an algebraic data type?

7. 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

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.

8. 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.