X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=exercises%2Fassignment5_answers.mdwn;h=9be28e21a5493191a8200d8f902c191878e38720;hp=0005ec6eb3a0c75a329d30d6932794405401a758;hb=0c65f3d6df4a89e41ba0ba01e39e35d4848ba5ca;hpb=4e747b63cdc33acc9acc95866ed2aa451524a90c diff --git a/exercises/assignment5_answers.mdwn b/exercises/assignment5_answers.mdwn index 0005ec6e..9be28e21 100644 --- a/exercises/assignment5_answers.mdwn +++ b/exercises/assignment5_answers.mdwn @@ -263,7 +263,7 @@ Choose one of these languages and write the following functions. let rec tree_best_sofar (t : 'a color_tree) (lead : maybe_leader) : maybe_leader * int = match t with - | Leaf a -> (None, a) + | Leaf a -> (lead, a) | Branch(l, col, r) -> let (lead',left_score) = tree_best_sofar l lead in let (lead'',right_score) = tree_best_sofar r lead' in @@ -437,6 +437,7 @@ Again, we've left some gaps. (The use of `type` for the first line in Haskell an type lambda_term = Var of identifier | Abstract of identifier * lambda_term | App of lambda_term * lambda_term + 16. Write a function `occurs_free` that has the following type: occurs_free : identifier -> lambda_term -> bool @@ -505,7 +506,7 @@ type `Bool`. also a mistake. What we want is a result whose type _is_ `Bool`, that is, `∀α. α -> α -> α`. `(q [Bool])` doesn't have that type, but rather the type `Bool -> Bool -> Bool`. The first, desired, type has an outermost `∀`. The second, wrong type doesn't; it only has `∀`s inside the antecedents and consequents of the various arrows. The last one of those could be promoted to be an outermost `∀`, since - `P -> ∀α. Q ≡ ∀α. P -> Q` when `α` is not free in `P`. But that couldn't be done with the others. + `P -> ∀α. Q` is equivalent to `∀α. P -> Q` when `α` is not free in `P`. But that couldn't be done with the others. The type `Nat` (for "natural number") may be encoded as follows: