Week 10: Notes

folds
type synonyms
algebraic datatypes
recursive data structures
derived instances

You can read about these subjects in Learn You A Haskell, chapters 6 and 8.

tutorial solutions

We solved these problems in Adam Dingle's tutorial:

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.

-- slice "abc" -> [('a', "bc"), ('b', "ac"), ('c', "ab")]
slice :: [a] -> [(a, [a])]
slice xs = slice1 [] xs where
  slice1 prefix [] = []
  slice1 prefix (x : xs) = (x, prefix ++ xs) : slice1 (prefix ++ [x]) xs

perms :: [a] -> [[a]]
perms [] = [[]]
perms xs = [ x : p | (x, ys) <- slice xs, p <- perms ys ]

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.

is_search_tree :: Ord a => Tree a -> Bool
is_search_tree tree = check Nothing tree Nothing where
  -- check min tree max returns true if tree is a valid binary search tree
  --    *and* all values in the tree are in the range (min, max)
  check :: Ord a => Maybe a -> Tree a -> Maybe a -> Bool
  check _min Nil _max = True
  check min (Node left x right) max =
    all (<x) min && all (x<) max &&
      check min left (Just x) && check (Just x) right max

Note: In this solution we've used the fact that all works on any Foldable type, including Maybe. We haven't yet talked in the lecture about the type class Foldable, but we will soon.

Tree Fold

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

tree_foldr :: (b -> a -> a) -> a -> Tree b -> a
tree_foldr f a Nil = a
tree_foldr f a (Node left x right) =
  let a1 = f x (tree_foldr f a right) in
  tree_foldr f a1 left

tree_sum :: Num a => Tree a -> a
tree_sum tree = tree_foldr (+) 0 tree

flatten :: Tree a -> [a]
flatten tree = tree_foldr (:) [] tree

We observed that using flatten we can solve the previous exercise much more easily:

-- Is a list in order?
in_order :: Ord a => [a] -> Bool
in_order [] = True
in_order [x] = True
in_order (x : y : ys) = x < y && in_order (y : ys)

is_search_tree :: Ord a => Tree a -> Bool
is_search_tree = in_order . flatten

I also mentioned that instead of writing tree_foldr above we can simply derive Foldable in our Tree definition:

data Tree a = Nil | Node (Tree a) a (Tree a)
  deriving (Show, Foldable)