Week 9: Exercises

1. Folding Minus

What are the values of these expressions?

1. foldl (-) 0 [1, 2, 3]

2. foldr (-) 0 [1, 2, 3]

2. Tree Values

Consider this definition of a binary tree:

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

For example, here is a binary tree:

It will have this representation:

    tree :: Tree Int
    tree = Node (Node Nil 2 Nil) 5 (Node (Node Nil 8 Nil) 10 (Node Nil 12 Nil))

Write a function treeVals that takes a binary search tree and returns a list of all its values in order:

treeVals :: Tree a -> [a]

How efficient is your function?

3. Valid Search Tree

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.

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

5. Algebraic Expressions

a) Design a data type Exp that can represent any arithmetic expression involving integer constants, named variables, and the +, - and * operators. Such expressions include

(x + y) * (x – y)
z * (z – 2)
14
0 + (1 + (2 + 3))

b) Write a function eval :: Exp -> [(String, Int)] -> Int that evaluates an expression given an environment, which is an association list that holds the variables of the variables in the expression.

6. Prefix Expressions

Write a function parse :: String -> Exp 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 :: Exp -> Exp 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. Combinations

Write a function that takes an integer K and a finite list of length N, with K ≤ N. The function should return a list of all combinations of K elements of the list.

9. Permutations

Write a function permutations :: [a] -> [[a]] that returns a list of all permutations of a given list. Do not assume that the type a implements Eq.