hints/assignment_6_commentary.mdwn

   1 Many of you offered a solution along the following lines:
   2
   3         type 'a state = int -> 'a * int;;
   4         let unit (a : 'a) : 'a state =
   5           fun count -> (a, count);;
   6         let bind (u : 'a state) (f : 'a -> 'b state ) : 'b state =
   7           fun count -> let (a, count') = u count in f a count';;
   8
   9         (* Looks good so far, now how are we going to increment the count? *)
  10
  11         let lift2 (f : 'a -> 'b -> 'c) (u : 'a state) (v : 'b state) : 'c state =
  12           bind u (fun x ->
  13             bind v (fun y ->
  14               fun count -> (f x y, count + 1)));;
  15
  16 Whoops. That will work for the cases you're probably thinking about. For instance, you can do:
  17
  18         lift2 (+) (unit 1) (lift2 (+) (unit 2) (unit 3));;
  19
  20 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.
  21
  22 However, there are several problems here. First off, you shouldn't name your function `lift2`, because we're using that name for a function that's interdefinable with `bind` in a specific way. Our canonical `lift2` function is:
  23
  24         let lift2 (f : 'a -> 'b -> 'c) (u : 'a state) (v : 'b state) : 'c state =
  25           bind u (fun x ->
  26             bind v (fun y ->
  27               unit (f x y)));;
  28
  29 (Haskell calls this `liftM2`, and calls our `lift` either `liftM` or `mapM`.)
  30
  31 OK, so then you might call your function `loft2` instead. So what?
  32
  33 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.
  34
  35 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:
  36
  37         let tick (a : 'a) : 'a state =
  38           fun count -> (a, count + 1);;
  39
  40         let result1 =
  41           bind
  42             (lift2 (+)
  43               (unit 1)
  44               (bind
  45                 (lift2 (+)
  46                   (unit 2)
  47                   (unit 3))
  48                 tick))
  49             tick;;
  50
  51         result1 0;; (* evaluates to (6, 2) *)
  52
  53 Or like this:
  54
  55         let tock : unit state =
  56           fun count -> ((), count + 1);;
  57
  58         let result2 =
  59           bind
  60             tock
  61             (fun _ -> lift2 (+)
  62               (unit 1)
  63               (bind
  64                 tock
  65                 (fun _ -> lift2 (+)
  66                   (unit 2)
  67                   (unit 3))));;
  68
  69         result2 0;; (* evaluates to (6, 2) *)
  70