Week 9: 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. 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.

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

8. Champernowne's Constant

Solve Project Euler #40 "Champernowne's Constant". Use an infinite list.