author jim Sat, 21 Mar 2015 07:49:42 +0000 (03:49 -0400) committer Linux User Sat, 21 Mar 2015 07:49:42 +0000 (03:49 -0400)

index e7b8274..fd73778 100644 (file)
@@ -291,7 +291,9 @@ Choose one of these languages and write the following functions.
let my_score = left_score + right_score in
let my_score = left_score + right_score in
+            | None -> Some(col,my_score), my_score
tree_walker leaf_handler joiner t

Then `tree_best` could be defined as in the direct answer.
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
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

aux [] t

@@ -352,8 +352,18 @@ In question 2 above, you defined `maybe_map2`. [[Before|assignment1]] we encount
<!-- 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.)

<!-- 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?

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 *)
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.
<!-- in Haskell, `liftA2 f xs ys` -->

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>
A similar choice between "zipping" and "crossing" could be made when `map2`-ing two trees. For example, the trees:

<pre>
@@ -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

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

| App (head, arg) -> occurs_free ident head || occurs_free ident arg

+

## Encoding Booleans, Church numerals, and Right-Fold Lists in System F ##

## Encoding Booleans, Church numerals, and Right-Fold Lists in System F ##