```        Red
/ \
Blue \
/ \  Green
a   b  / \
c   Red
/ \
d   e
```
(for any leaf values `a` through `e`), it should return:
```        Red
/ \
Blue \
/ \  Green
1   1  / \
1   Red
/ \
2   2
```
9. (More challenging.) Assume you have a `color_tree` whose leaves are labeled with `int`s (which may be negative). For this problem, assume also that no color labels multiple `Branch`s (non-leaf nodes). Write a recursive function that reports which color has the greatest "score" when you sum up all the values of its descendent leaves. Since some leaves may have negative values, the answer won't always be the color at the tree root. In the case of ties, you can return whichever of the highest scoring colors you like. ## Search Trees ## (More challenging.) For the next problem, assume the following type definition: (* OCaml *) type search_tree = Nil | Inner of search_tree * int * search_tree -- Haskell data Search_tree = Nil | Inner Search_tree Int Search_tree deriving (Show) That is, its leaves have no labels and its inner nodes are labeled with `int`s. Additionally, assume that all the `int`s in branches descending to the left from a given node will be less than the `int` of that parent node, and all the `int`s in branches descending to the right will be greater. We can't straightforwardly specify this constraint in OCaml's or Haskell's type definitions. We just have to be sure to maintain it by hand. 10. Write a function `search_for` with the following type, as displayed by OCaml: type direction = Left | Right search_for : int -> search_tree -> direction list option Haskell would say instead: data Direction = Left | Right deriving (Eq, Show) search_for :: Int -> Search_tree -> Maybe [Direction] Your function should search through the tree for the specified `int`. If it's never found, it should return the value OCaml calls `None` and Haskell calls `Nothing`. If it finds the `int` right at the root of the `search_tree`, it should return the value OCaml calls `Some []` and Haskell calls `Just []`. If it finds the `int` by first going down the left branch from the tree root, and then going right twice, it should return `Some [Left; Right; Right]` or `Just [Left, Right, Right]`. ## More Map2s ## In question 2 above, you defined `maybe_map2`. [[Before|assignment1]] we encountered `map2` for lists. There are in fact several different approaches to mapping two lists together. 11. One approach is to apply the supplied function to the first element of each list, and then to the second element of each list, and so on, until the lists are exhausted. If the lists are of different lengths, you might stop with the shortest, or you might raise an error. Different implementations make different choices about that. Let's call this function: (* OCaml *) map2_zip : ('a -> 'b -> 'c) -> ('a) list -> ('b) list -> ('c) list Write a recursive function that implements this, in Haskell or OCaml. Let's say you can stop when the shorter list runs out, if they're of different lengths. (OCaml and Haskell each already have functions in their standard libraries --- `map2` or `zipWith` -- that do this. And it also corresponds to a list comprehension you can write in Haskell like this: :set -XParallelListComp [ f x y | x <- xs | y <- ys ] But we want you to write this function from scratch.) 12. What is the relation between the function you just wrote, and the `maybe_map2` function you wrote for problem 2, above? 13. Another strategy is to take the *cross product* of the two lists. If the function: (* OCaml *) map2_cross : ('a -> 'b -> 'c) -> ('a) list -> ('b) list -> ('c) list is applied to the arguments `f`, `[x0, x1, x2]`, and `[y0, y1]`, then the result should be: `[f x0 y0, f x0 y1, f x1 y0, f x1 y1, f x2 y0, f x2 y1]`. Write this function. A similar choice between "zipping" and "crossing" could be made when `map2`-ing two trees. For example, the trees:
```    0       5
/ \     / \
1   2   6   7
/ \         / \
3  4        8  9
```
could be "zipped" like this (ignoring any parts of branches on the one tree that extend farther than the corresponding branch on the other):
```   f 0 5
/    \
f 1 6  f 2 7
```