hints/assignment_10_hint_2.mdwn

   1 I'd work with a tree monadized with a `Continuation_monad`, that is, with:
   2
   3     #use "path/to/tree_monadize.ml";;
   4
   5 You could in theory also use the richer "monads.ml" library:
   6
   7     #use "path/to/monads.ml";;
   8     module TC = Tree_monad.T(Continuation_monad);;
   9     let tree_monadize = TC.distribute;;
  10
  11 But I found it easier to work out the solution using the simpler "tree\_monadize.ml" library. The "monadize.ml" library enforces encapsulation in a way that's nice and sanitized, but makes experimentation more cumbersome.
  12
  13
  14 It makes debugging easier if we work with a tree whose starting leaf
  15 elements are differently typed than the tree we aim to finish with. So:
  16
  17     let tree = Node(Leaf '1', Node(Leaf '2', Node(Leaf '3', Leaf '1')));;
  18
  19 Now, we already know how to count the leaves using a Continuation monad
  20 in tree shape:
  21
  22     let v0 = TreeCont.monadize (fun a k -> 1 + k a) tree (fun t -> 0);;
  23
  24 There are two interesting functions here: we'll call them the "distributed" function `fun a k -> 1 + k a` and the "seed" function `fun t -> 0`.
  25
  26 Our first step is to extend `v0` so that we count how many leaves there are
  27 of each value, rather than how many leaves in total:
  28
  29     let update_env e x = fun y -> (if x = y then 1 else 0) + e y;;
  30
  31     let v1 = TreeCont.monadize (fun a k ->
  32           fun e0 ->
  33             let ecur = k a e0
  34         in update_env ecur a
  35     ) tree (fun t e -> e) (fun a -> 0);;
  36
  37         (* now
  38        v1 '0' ~~> 0
  39        v1 '1' ~~> 2
  40        v1 '2' ~~> 1
  41          *)
  42
  43 How does this work? Our distributed function `fun a k -> ...` takes a leaf element `a` and a continuation `k`, which maps leaf elements and environments `e0` to new environments `ecur`. It gives back a function from `e0` to an updated version of `ecur`.
  44
  45 Our seed function here is the initial continuation. Instead of taking a leaf element and an env, it takes a tree of such elements and an env. In general, wherever the distributed function takes `'a`s, the seed function takes `'a tree`s.
  46
  47 Here our seed function just ignores the tree and returns the env unchanged.
  48
  49 What that gives us is a function from environments to environments. We give it
  50 an initial environment `fun a -> 0` to get started. We get back an
  51 environment `v1` that maps each leaf element to how many times that leaf
  52 element appeared in the tree we started with.
  53
  54 OK? You might want to stop reading here, and see how much further you
  55 can get on your own.
  56
  57 But there are [more hints](/hints/assignment_10_hint_3) if you need them.