X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=exercises%2F_assignment7.mdwn;h=793a15e46c8715b5f99f5ac833f5c6e59fc96456;hp=cd798ab078ad9b86f986a8f40d396a487b579c3b;hb=7888d341776f23849c60cd82ca816ed13e5bc9c2;hpb=ef351afc1578508e294f73be1c2f2445463d6383 diff --git a/exercises/_assignment7.mdwn b/exercises/_assignment7.mdwn index cd798ab0..793a15e4 100644 --- a/exercises/_assignment7.mdwn +++ b/exercises/_assignment7.mdwn @@ -1,25 +1,18 @@ -# 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: - + (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. - - + let bind' (u: int option) (f: int -> (int option)) = + match u with None -> None | Some x -> f x;;