X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=exercises%2Fassignment5.mdwn;h=5dd1cbb24a6f8982e29b464a4d6a262d7b6675ae;hp=0494fa7d5f379e62aaea4473aca4bfab152e59e7;hb=442a8534983a824eec968ce2bb113fe60e0b1007;hpb=3b82c6f6da5e92a42e99b6afd2c5b7e4d6a75f67
diff --git a/exercises/assignment5.mdwn b/exercises/assignment5.mdwn
index 0494fa7d..5dd1cbb2 100644
--- a/exercises/assignment5.mdwn
+++ b/exercises/assignment5.mdwn
@@ -144,7 +144,7 @@ Choose one of these languages and write the following functions.
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 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 ##
@@ -252,6 +252,8 @@ Again, we've left some gaps. (The use of `type` for the first line in Haskell an
15. Choose one of these languages and fill in the gaps to complete the definition.
+
+
16. Write a function `occurs_free` that has the following type:
occurs_free : identifier -> lambda_term -> bool
@@ -329,7 +331,7 @@ any type `Î±`, as long as your function is of type `Î± -> Î±` and you have a bas
-- 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; ... }
@@ -384,6 +386,8 @@ Yet we haven't given ourselves the capacity to talk about `list [S]` and so on 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.
@@ -406,7 +410,7 @@ Be sure to test your proposals with simple lists. (You'll have to `sysf_cons` up
# 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".