author Jim Pryor Sun, 5 Dec 2010 17:54:05 +0000 (12:54 -0500) committer Jim Pryor Sun, 5 Dec 2010 17:54:05 +0000 (12:54 -0500)
Signed-off-by: Jim Pryor <profjim@jimpryor.net>
 assignment6.mdwn patch | blob | history hints/assignment_6_commentary.mdwn [new file with mode: 0644] patch | blob

index 5f8c1b6..82aee95 100644 (file)
@@ -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]].

+       <div style="color: red">See our [commentary](/hints/assignment_6_commentary) on your solutions.</div>
+
+
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 (file)
index 0000000..df757cb
--- /dev/null
@@ -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) *)
+