hints/assignment_10_hint_3.mdwn

   1 OK, here's the next step.
   2
   3 We'll switch gears and work without the Continuation monad for a while
   4 (though eventually we'll come back there).
   5
   6 We already know how to annotate the leaves of a tree as we visit
   7 them:
   8
   9     (* annotate leaves as they're visited *)
  10
  11     let annotater : int -> (int * int) State_monad.m =
  12       fun (a : int) -> fun s -> ((a,s+1), s+1);;
  13
  14     let initial_store = 0 in
  15     TreeState.monadize annotater t1 initial_store;;
  16
  17
  18 Let's try something similar, only this time we'll re-define our State
  19 monad so as to have a more complex store. We want our store to be not a
  20 simple `int`, but instead a `char -> int` environment.
  21
  22     module State_custom = struct
  23         type store = char -> int
  24         type 'a m = store -> ('a * store)
  25         let unit a : 'a m = fun s -> (a,s)
  26         let bind (u: 'a m) (f: 'a -> 'b m) : 'b m =
  27             fun s -> let (a,s') = u s in f a s'
  28     end;;
  29     module TS = Tree_monadizer(State_custom);;
  30
  31
  32 While we're at it, let's re-define our Reader monad too:
  33
  34     module Reader_custom = struct
  35         type env = char -> int
  36         type 'a m = env -> 'a
  37         let unit a : 'a m = fun e -> a
  38         let bind (u: 'a m) (f: 'a -> 'b m) : 'b m =
  39             fun e -> f (u e) e
  40     end;;
  41     module TR = Tree_monadizer(Reader_custom);;
  42
  43
  44 Now instead of annotating leaves with the current store, we'll convert
  45 the leaves into "askers" that will wait for an environment and return what that
  46 environment says about the original leaf. At the same time, we'll update the store so that it knows how many leafs of each value have been seen:
  47
  48
  49     let annotater : char -> ((char -> int) -> int) State_custom.m =
  50         fun a s -> ((fun e -> e a), update_env s a);;
  51
  52     let v2 = TS.monadize annotater tree (fun a -> 0);;
  53
  54
  55 The seed function here is an environment that by default maps every leaf
  56 element to 0. In the end, `v2` consists of a pair of a tree of askers, and a
  57 `char -> int` environment. We can use `TR.monadize` to convert that tree of
  58 askers into a tree-asker, that is, a function from an environment to a tree. And we then feed it the very environment that was `v2`'s final store:
  59
  60     let (tree',env) = v2
  61     in TR.monadize (fun a -> a) tree' env;;
  62
  63
  64 This gives us a tree of `int`s, where each `int` replaces the original `char`
  65 with the number of times the `char` appeared in the original tree.
  66
  67
  68
  69 We've got our answer, but the way we did it boils down to asking for two traversals. Can we do better?
  70
  71
  72 That's debatable. It won't be possible to avoid two traversals taking place,
  73 somewhere. But we can try to avoid *asking* for two traversals. We can aim for
  74 code that only asks for a single traversal---whatever else is needed gets
  75 forced by the plumbing.
  76
  77 Will doing so make our program clearer? No, probably not. But it should be
  78 a useful step towards a better understanding of continuations.
  79
  80
  81 How shall we do it? Instead of a State monad paired with
  82 Reader monad, let's use a Continuation monad paired with Reader monad.
  83 The Continuation monad will take over the State monad's job of modifying the
  84 environment we're working with.
  85
  86
  87 OK? You might want to stop reading here, and see how much further you
  88 can get on your own.
  89
  90 But there's [a solution and explanation](/hints/assignment_10_hint_4) posted if you need them.