From ce6251343f916dcbfeb7160aff5b1312fa31ce7f Mon Sep 17 00:00:00 2001 From: Jim Pryor Date: Sun, 5 Dec 2010 12:54:05 -0500 Subject: [PATCH] commentary on ass6 solutions Signed-off-by: Jim Pryor --- assignment6.mdwn | 3 ++ hints/assignment_6_commentary.mdwn | 68 ++++++++++++++++++++++++++++++++++++++ 2 files changed, 71 insertions(+) create mode 100644 hints/assignment_6_commentary.mdwn diff --git a/assignment6.mdwn b/assignment6.mdwn index 5f8c1b65..82aee95f 100644 --- a/assignment6.mdwn +++ b/assignment6.mdwn @@ -24,6 +24,9 @@ your solution). You'll need to define a computation monad type, unit, bind, and lift2. We encourage you to consider this hint: [[hints/Assignment 6 Hint 1]]. +
See our [commentary](/hints/assignment_6_commentary) on your solutions.
+ + 2. Prove that your monad satisfies the monad laws. First, give examples illustrating specific cases in which the monad laws are obeyed, then explain (briefly, not exhaustively) why the laws hold in diff --git a/hints/assignment_6_commentary.mdwn b/hints/assignment_6_commentary.mdwn new file mode 100644 index 00000000..df757cbc --- /dev/null +++ b/hints/assignment_6_commentary.mdwn @@ -0,0 +1,68 @@ +Many of you offered a solution along the following lines: + + type 'a state = int -> 'a * int;; + let unit (a : 'a) : 'a state = + fun count -> (a, count);; + let bind (u : 'a state) (f : 'a -> 'b state ) : 'b state = + fun count -> let (a, count') = u count in f a count';; + + (* Looks good so far, now how are we going to increment the count? *) + + let lift2 (f : 'a -> 'b -> 'c) (u : 'a state) (v : 'b state) : 'c state = + bind u (fun x -> + bind v (fun y -> + fun count -> (f x y, count + 1)));; + +Whoops. That will work for the cases you're probably thinking about. For instance, you can do: + + lift2 (+) (unit 1) (lift2 (+) (unit 2) (unit 3));; + +and you'll get back an `int state` that when applied to a starting count of `0` yields the result `(6, 2)`---that is, the result of the computation was 6 and the number of operations was 2. + +However, there are several problems here. First off, you shouldn't name your function `lift`, because we're using that name for a function that's interdefinable with `bind` in a specific way. Our canonical `lift` function (also called `mapM` and `liftM` in Haskell) is: + + let lift2 (f : 'a -> 'b -> 'c) (u : 'a state) (v : 'b state) : 'c state = + bind u (fun x -> + bind v (fun y -> + unit (f x y)));; + +OK, so then you might call your function `loft2` instead. So what? + +The remaining problem is more subtle. It's that your solution isn't very modular. You've crafted a tool `loft2` that fuses the operation of incrementing the count with the behavior of our `lift2`. What if we needed to deal with some unary functions as well? Then you'd need a `loft1`. What if we need to deal with some functions that are already monadic? Then you'd need a tool that fuses the count-incrementing with the behavior of `bind`. And so on. + +It's nicer to just create a little module that does the count-incrementing, and then use that together with the pre-existing apparatus of `bind` and (our canonical) `lift` and `lift2`. You could do that like this: + + let tick (a : 'a) : 'a state = + fun count -> (a, count + 1);; + + let result1 = + bind + (lift2 (+) + (unit 1) + (bind + (lift2 (+) + (unit 2) + (unit 3)) + tick)) + tick;; + + result1 0;; (* evaluates to (6, 2) *) + +Or like this: + + let tock : unit state = + fun count -> ((), count + 1);; + + let result2 = + bind + tock + (fun _ -> lift2 (+) + (unit 1) + (bind + tock + (fun _ -> lift2 (+) + (unit 2) + (unit 3))));; + + result2 0;; (* evaluates to (6, 2) *) + -- 2.11.0