-# Assignment 6 (week 7)
+## Baby monads
-## Evaluation order in Combinatory Logic
+(Depends on lecture notes for safe division by zero.)
-1. Give a term that the lazy evaluators (either the Haskell evaluator,
-or the lazy version of the OCaml evaluator) do not evaluate all the
-way to a normal form, i.e., that contains a redex somewhere inside of
-it after it has been reduced.
+Write a function `lift'` that generalized the correspondence between +
+and `add'`: that is, `lift'` takes any two-place operation on integers
+and returns a version that takes arguments of type `int option`
+instead, returning a result of `int option`. In other words, `lift'`
+will have type:
-<!-- reduce3 (FA (K, FA (I, I))) -->
+ (int -> int -> int) -> (int option) -> (int option) -> (int option)
+so that `lift' (+) (Some 3) (Some 4)` will evalute to `Some 7`.
+Don't worry about why you need to put `+` inside of parentheses.
+You should make use of `bind'` in your definition of `lift'`:
-2. One of the
-[[criteria we established for classifying reduction strategies|
-topics/week3_evaluation_order]]
-strategies is whether they reduce subexpressions hidden under lambdas.
-That is, for a term like `(\x y. x z) (\x. x)`, do we reduce to
-`\y.(\x.x) z` and stop, or do we reduce further to `\y.z`? Explain
-what the corresponding question would be for CL. Using either the
-OCaml CL evaluator or the Haskell evaluator developed in the wiki
-notes, prove that the evaluator does reduce expressions inside of
-"functional" CL expressions. Then provide a modified evaluator that
-does not perform reductions in those positions.
-
-<!-- just add early no-op cases for Ka and Sab -->
-
-3. Converting to lambdas. Using the type definitions you developed in
-homework 5, rebuild the evaluator in OCaml to handle the untyped
-lambda calculus. Making use of the occurs_free function you built,
-we'll provide a function that performs safe substitution.
-
+ let bind' (u: int option) (f: int -> (int option)) =
+ match u with None -> None | Some x -> f x;;