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 We could proceed in two ways: we could either convert the leafs into "askers" now, and then use `TR.monadize` to conver the tree of askers into a tree-asker (that is, a function from an environment to a tree). Or we could just pass the leaves through unchanged for the moment, and leave the job of converting them to askers to the `TR.monadize` pass. We'll take the second strategy. (This turns out to fit better with what we go on to do later.) Hence, this first pass, using `TS.monadize`, only has to update the store.
  49
  50
  51     let annotater : char -> char State_custom.m =
  52         fun a s -> (a, update_env s a);;
  53
  54     let v2 = TS.monadize annotater tree (fun a -> 0);;
  55
  56
  57 The seed function here is an environment that by default maps every leaf
  58 element to 0. In the end, `v2` consists of a pair of a tree and a
  59 `char -> int` environment. We can use `TR.monadize` to convert that tree 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:
  60
  61     let asker : char -> int Reader_custom.m =
  62       fun (a : char) -> fun (env : char -> int) -> env a;;
  63
  64     let (t, env) = v2
  65     in TR.monadize asker t env;;
  66
  67
  68 This gives us a tree of `int`s, where each `int` replaces the original `char`
  69 with the number of times the `char` appeared in the original tree.
  70
  71
  72
  73 We've got our answer, but the way we did it boils down to asking for two traversals. Can we do better?
  74
  75
  76 That's debatable. It won't be possible to avoid two traversals taking place,
  77 somewhere. But we can try to avoid *asking* for two traversals. We can aim for
  78 code that only asks for a single traversal---whatever else is needed gets
  79 forced by the plumbing.
  80
  81 Will doing so make our program clearer? No, probably not. But it should be
  82 a useful step towards a better understanding of continuations.
  83
  84
  85 How shall we do it? Instead of a State monad paired with
  86 Reader monad, let's use a Continuation monad paired with Reader monad.
  87 The Continuation monad will take over the State monad's job of modifying the
  88 environment we're working with.
  89
  90
  91 OK? You might want to stop reading here, and see how much further you
  92 can get on your own.
  93
  94 But there's [a solution and explanation](/hints/assignment_10_hint_4) posted if you need them.