Week 10: Exercises

1. Permutations

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

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

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