From: jim Date: Mon, 6 Apr 2015 08:40:49 +0000 (-0400) Subject: refine assignment X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=commitdiff_plain;h=7deed75036fa6bac000efdfdbd3d2f8ebbc26960;ds=inline refine assignment --- diff --git a/exercises/assignment8.mdwn b/exercises/assignment8.mdwn index 4778eec0..e6d24837 100644 --- a/exercises/assignment8.mdwn +++ b/exercises/assignment8.mdwn @@ -64,6 +64,24 @@ Return to the original code (that is, before the modifications required by the p let xx = S.(mid 1 >>= fun x -> put 20 >> modify succ >> get >>= fun y -> mid [x;y]) in S.run xx 0 + Recall that `xx >> yy` is short for `xx >>= fun _ -> yy`. The equivalent Haskell code is: + + import Control.Monad.State + let { xx :: State Int [Int]; + xx = return 1 >>= \x -> put 20 >> modify succ >> get >>= \y -> return [x,y] } in + runState xx 0 + + Or: + + import Control.Monad.State + let { xx :: State Int [Int]; + xx = do { x <- return 1; + put 20; + modify succ; + y <- get; + return [x,y] } } in + runState xx 0 + Don't try running the code yet. Instead, get yourself into a position to predict what it will do, by reading the past few discussions about the State monad. After you've made a prediction, then run the code and see if you got it right. 6. Here's another one: @@ -73,11 +91,19 @@ Return to the original code (that is, before the modifications required by the p xx >>= fun x1 -> xx >>= fun x2 -> xx >>= fun x3 -> mid [x1;x2;x3]) in S.run yy 0 - What is your prediction? What did OCaml actually evaluate this to? + The equivalent Haskell code is: + + import Control.Monad.State + let { xx :: State Int Int; + xx = modify succ >> get; + yy = xx >>= \x1 -> xx >>= \x2 -> xx >>= \x3 -> return [x1,x2,x3] } in + runState yy 0 + + What is your prediction? What did OCaml or Haskell actually evaluate this to? 7. Suppose you're trying to use the State monad to keep a running tally of how often certain arithmetic operations have been used in computing a complex expression. You've come upon the design plan of using the same State monad module `S` from the previous problems, and defining a function like this: - let counting_plus xx yy = S.(map2 (+) xx yy >>= tick) + let counting_plus xx yy = S.(tick >> map2 (+) xx yy) How should you define the operation `tick` to make this work? The intended behavior is that after running: @@ -88,10 +114,12 @@ Return to the original code (that is, before the modifications required by the p 8. Instead of the design in the previous problem, suppose you had instead chosen to do things this way: - let counting_plus xx yy = S.(tock >> map2 (+) xx yy) + let counting_plus xx yy = S.(map2 (+) xx yy >>= tock) How should you define the operation `tock` to make this work, with the same behavior as before? + + 9. Here is how to create a monadic stack of a Reader monad transformer wrapped around an underlying Option monad: module O = Monad.Option (* not really necessary *) @@ -103,7 +131,13 @@ Return to the original code (that is, before the modifications required by the p let env0 = (* some appropriate env, depending on how you defined R *) in let xx = RO.(mid 1) in RO.run xx env0 - and inspecting the type of the result. Okay, here are some questions about various monad transformers. Use OCaml to help you answer them. Which combined monad has the type of an optional list (that is, either `None` or `Some [...]`): an Option transformer wrapped around an underlying List monad, or a List transformer wrapped around an underlying Option monad? Which combined monad has the type of a function from `store`s to a pair `('a list, store)`: a List transformer wrapped around an underlying State monad or a State transformer wrapped around an underlying List monad? + and inspecting the type of the result. In Haskell: + + import Control.Monad.Reader + -- substitute your own choices for the type Env and value env0 + let { xx :: ReaderT Env Maybe Int; xx = return 1 } in runReaderT xx env0 + + Okay, here are some questions about various monad transformers. Use OCaml to help you answer them. Which combined monad has the type of an optional list (that is, either `None` or `Some [...]`): an Option transformer wrapped around an underlying List monad, or a List transformer wrapped around an underlying Option monad? Which combined monad has the type of a function from `store`s to a pair `('a list, store)`: a List transformer wrapped around an underlying State monad or a State transformer wrapped around an underlying List monad? The last two problems are non-monadic. @@ -113,7 +147,7 @@ The last two problems are non-monadic. let incr c = (let old = !cell in let () = cell := old + 1 in ()) in (incr cell, !cell, incr cell, incr cell) - will evaluate to will be `((), n, (), ())` for some number `n` between `0` and `3`. But what number is sensitive to the details of OCaml's evaluation strategy for evaluating tuple expressions. How can you avoid that dependence? That is, how can you rewrite such code to force it that the values in the triple have been evaluated left-to-right? Show us a strategy that works no matter what the expressions in the tuple are, not just these particular ones. (But you can assume that the expressions all terminate.) + will evaluate to will be `((), n, (), ())` for some number `n` between `0` and `3`. But what number is sensitive to the details of OCaml's evaluation strategy for evaluating tuple expressions. How can you avoid that dependence? That is, how can you rewrite such code to force it that the values in the 4-tuple have been evaluated left-to-right? Show us a strategy that works no matter what the expressions in the tuple are, not just these particular ones. (But you can assume that the expressions all terminate.) 11. In the evaluator code for [[Week 7 homework|/exercises/assignment7]], we left the `LetRec` portions unimplemented. How might we implement these for the second, `env`-using interpreter? One strategy would be to interpret expressions like: @@ -138,6 +172,8 @@ The last two problems are non-monadic. OK, once you've done that, then add an extra line: - | LetRec of identifier * identifier * term * term + | LetRec of identifier * term * term + + to the definition of the `term` datatype. (For `letrec IDENT1 = TERM1 in TERM2`. You can assume that `TERM1` is always a `Lambda` term.) Now what will you need to add to the `eval` function to get it to interpret these terms properly? This will take some thought, and a good understanding of how the other clauses in the `eval` function are working. - to the definition of the `term` datatype. (For `letrec IDENT1 = \IDENT2. TERM1 in TERM2`.) Now what will you need to add to the `eval` function to get it to interpret these terms properly? This will take some thought, and a good understanding of how the other clauses in the `eval` function are working. + Here's a conceptual question: why did we point you in the direction of complicating the type that environments associate variables with, rather than just adding a new clause to the `result` type, as we did with Closures?