Date: Sat, 21 Mar 2015 03:49:42 -0400
Subject: [PATCH] add some more
---
exercises/assignment5_answers.mdwn | 34 ++++++++++++++++++++++++++--------
1 file changed, 26 insertions(+), 8 deletions(-)
diff --git a/exercises/assignment5_answers.mdwn b/exercises/assignment5_answers.mdwn
index e7b82745..fd737786 100644
--- a/exercises/assignment5_answers.mdwn
+++ b/exercises/assignment5_answers.mdwn
@@ -291,7 +291,9 @@ Choose one of these languages and write the following functions.
let (leader',left_score) = lh leader in
let (leader'',right_score) = rh leader' in
let my_score = left_score + right_score in
- (match leader'' with | None -> Some(col,my_score), my_score | Some(_,leader_score) -> (if my_score > leader_score then Some(col,my_score) else leader''), my_score) in
+ (match leader'' with
+ | None -> Some(col,my_score), my_score
+ | Some(_,leader_score) -> (if my_score > leader_score then Some(col,my_score) else leader''), my_score) in
tree_walker leaf_handler joiner t
Then `tree_best` could be defined as in the direct answer.
@@ -327,11 +329,9 @@ That is, its leaves have no labels and its inner nodes are labeled with `int`s.
let rec aux (trace : direction list) t =
match t with
| Nil -> None
- | Inner(_,x,_) when x = sought -> Some(List.rev trace)
- | Inner(l,_,r) ->
- (match aux (Left :: trace) l with
- | None -> aux (Right :: trace) r
- | _ as result -> result) in
+ | Inner(l,x,r) when sought < x -> aux (Left::trace) l
+ | Inner(l,x,r) when sought > x -> aux (Right::trace) r
+ | _ -> Some(List.rev trace) in
aux [] t
@@ -352,8 +352,18 @@ In question 2 above, you defined `maybe_map2`. [[Before|assignment1]] we encount
But we want you to write this function from scratch.)
+ HERE IS AN OCAML ANSWER:
+
+ let rec map2_zip f xs ys =
+ match xs, ys with
+ | [], _ -> []
+ | _, [] -> []
+ | x'::xs', y'::ys' -> f x' y' :: map2_zip f xs' ys'
+
12. What is the relation between the function you just wrote, and the `maybe_map2` function you wrote for problem 2, above?
+ ANSWER: option/Maybe types are like lists constrained to be of length 0 or 1.
+
13. Another strategy is to take the *cross product* of the two lists. If the function:
(* OCaml *)
@@ -362,6 +372,13 @@ In question 2 above, you defined `maybe_map2`. [[Before|assignment1]] we encount
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.
+ HERE IS AN OCAML ANSWER:
+
+ let rec map2_cross f xs ys =
+ match xs with
+ | [] -> []
+ | x'::xs' -> List.append (List.map (f x') ys) (map2_cross f xs' ys)
+
A similar choice between "zipping" and "crossing" could be made when `map2`-ing two trees. For example, the trees:
@@ -429,10 +446,11 @@ Again, we've left some gaps. (The use of `type` for the first line in Haskell an
let rec occurs_free (ident : identifier) (term : lambda_term) : bool =
match term with
- | Var var_ident -> ident = var_indent (* `x` is free in Var "x" but not in Var "y" *)
- | Abstract(bound_ident, term') -> ident <> bound_ident && occurs_free ident term' (* `x` is free in \y. x but not in \x. blah or \y. y *)
+ | Var var_ident -> ident = var_ident (* `x` is free in Var "x" but not in Var "y" *)
+ | Abstract(bound_ident, body) -> ident <> bound_ident && occurs_free ident body (* `x` is free in \y. x but not in \x. blah or \y. y *)
| App (head, arg) -> occurs_free ident head || occurs_free ident arg
+
## Encoding Booleans, Church numerals, and Right-Fold Lists in System F ##
--
2.11.0