Week 9: Exercises

1. Combinations

Write a function that takes an integer K ≥ 0 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.

2. Partitions

A partition of a positive integer n is a set of positive integers that add up to n. For example, the number 4 has 5 partitions:

1 + 1 + 1 + 1
2 + 1 + 1
2 + 2
3 + 1
4

Write a function partitions :: Int -> [[Int]] that produces a list of all partitions of a positive integer.

3. Flattening a Tree

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

In the lecture we wrote a function flatten that takes a binary tree and returns a list of all its values in order:

flatten :: Tree a -> [a]
flatten Nil = []
flatten (Node left x right) =
    flatten left ++ [x] ++ flatten right

This function runs in O(N²) in the worst case for a tree with N values. Rewrite the function so that it runs in O(N).

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

5. Tree Fold

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

6. Tree Insertion

Write a function that can insert a value into a binary search tree. Choose an appropriate type for your function.
Using the function you wrote in part (a), write a function that inserts all values in a given list into a binary search tree.

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

8. Infinite Tree

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

9. Lists and Integers

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

10. Prefix Expressions

Consider expression trees as we defined them in the lecture:

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.

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