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.
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
<!-- or `f <$/fmap> ZipList xs <*/ap> ZipList ys`; or `pure f <*> ...`; or `liftA2 f (ZipList xs) (ZipList ys)` -->
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 *)
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.
<!-- in Haskell, `liftA2 f xs ys` -->
+ 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:
<pre>
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 ##