2 2
</pre>
-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 the the same color never labels multiple inner branches. 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.
+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 ##
15. Choose one of these languages and fill in the gaps to complete the definition.
+<a id="occurs_free"></a>
16. Write a function `occurs_free` that has the following type:
occurs_free : identifier -> lambda_term -> bool
-- Or this:
let sysf_true = (\y n -> y) :: Sysf_bool a
- Note that in both OCaml and the Haskell code, the generalization `∀'a` on the free type variable `'a` is implicit. If you really want to, you can supply it explicitly in Haskell by saying:
+ Note that in both OCaml and Haskell code, the generalization `∀α` on the free type variable `α` is implicit. If you really want to, you can supply it explicitly in Haskell by saying:
:set -XExplicitForAll
let { sysf_true :: forall a. Sysf_bool a; ... }
= λf:T -> S. λxs:list. xs [T] [list [S]] (λx:T. λys:list [S]. cons [S] (f x) ys) (nil [S])
-->
+*Update: Never mind, don't bother with the next three questions. They proved to be more difficult to implement in OCaml than we expected. Here is [[some explanation|assignment5 hint4]].*
+
19. Convert this list encoding and the `map` function to OCaml or Haskell. Again, call the type `sysf_list`, and the functions `sysf_nil`, `sysf_cons`, and `sysf_map`, to avoid collision with the names for native lists and functions in these languages. (In OCaml and Haskell you *can* say `('t) sysf_list` or `Sysf_list t`.)
20. Also give us the type and definition for a `sysf_head` function. Think about what value to give back if its argument is the empty list. It might be cleanest to use the `option`/`Maybe` technique explored in questions 1--2, but for this assignment, just pick a strategy, no matter how clunky.
# k 1 true ;;
- : int = 1
- If you can't understand how one term can have several types, recall our discussion in this week's notes of "principal types". (WHERE?)
+ If you can't understand how one term can have several types, recall our discussion in this week's notes of "principal types".