projects
/
lambda.git
/ blobdiff
commit
grep
author
committer
pickaxe
?
search:
re
summary
|
shortlog
|
log
|
commit
|
commitdiff
|
tree
raw
|
inline
| side by side
edits
[lambda.git]
/
manipulating_trees_with_monads.mdwn
diff --git
a/manipulating_trees_with_monads.mdwn
b/manipulating_trees_with_monads.mdwn
index
4f91bbb
..
0d9e33d
100644
(file)
--- a/
manipulating_trees_with_monads.mdwn
+++ b/
manipulating_trees_with_monads.mdwn
@@
-57,7
+57,7
@@
new leaves, and maps that function over all the leaves in the tree,
leaving the structure of the tree unchanged. For instance:
let double i = i + i;;
leaving the structure of the tree unchanged. For instance:
let double i = i + i;;
- tree_map
t1 double
;;
+ tree_map
double t1
;;
- : int tree =
Node (Node (Leaf 4, Leaf 6), Node (Leaf 10, Node (Leaf 14, Leaf 22)))
- : int tree =
Node (Node (Leaf 4, Leaf 6), Node (Leaf 10, Node (Leaf 14, Leaf 22)))
@@
-80,7
+80,7
@@
each leaf instead, by supplying the appropriate `int -> int` operation
in place of `double`:
let square i = i * i;;
in place of `double`:
let square i = i * i;;
- tree_map
t1 square
;;
+ tree_map
square t1
;;
- : int tree =
Node (Node (Leaf 4, Leaf 9), Node (Leaf 25, Node (Leaf 49, Leaf 121)))
- : int tree =
Node (Node (Leaf 4, Leaf 9), Node (Leaf 25, Node (Leaf 49, Leaf 121)))
@@
-140,7
+140,7
@@
It would be a simple matter to turn an *integer* into an `int reader`:
asker 2 (fun i -> i + i);;
- : int = 4
asker 2 (fun i -> i + i);;
- : int = 4
-
This
is a monadic box that waits for an an environment (here, the argument `modifier`) and returns what that environment maps `a` to.
+
`asker a`
is a monadic box that waits for an an environment (here, the argument `modifier`) and returns what that environment maps `a` to.
How do we do the analagous transformation when our `int`s are scattered over the leaves of a tree? How do we turn an `int tree` into a reader?
A tree is not the kind of thing that we can apply a
How do we do the analagous transformation when our `int`s are scattered over the leaves of a tree? How do we turn an `int tree` into a reader?
A tree is not the kind of thing that we can apply a
@@
-293,7
+293,7
@@
it through:
Later, we will talk more about controlling the order in which nodes are visited.
One more revealing example before getting down to business: replacing
Later, we will talk more about controlling the order in which nodes are visited.
One more revealing example before getting down to business: replacing
-`state` everywhere in `tree_monadize` with `list`
gives us
+`state` everywhere in `tree_monadize` with `list`
lets us do:
# let decider i = if i = 2 then [20; 21] else [i];;
# tree_monadize decider t1;;
# let decider i = if i = 2 then [20; 21] else [i];;
# tree_monadize decider t1;;
@@
-311,11
+311,11
@@
one for each choice of `int`s for its leaves.
Now for the main point. What if we wanted to convert a tree to a list
of leaves?
Now for the main point. What if we wanted to convert a tree to a list
of leaves?
- type ('
a, 'r
) continuation = ('a -> 'r) -> 'r;;
+ type ('
r,'a
) continuation = ('a -> 'r) -> 'r;;
let continuation_unit a = fun k -> k a;;
let continuation_bind u f = fun k -> u (fun a -> f a k);;
let continuation_unit a = fun k -> k a;;
let continuation_bind u f = fun k -> u (fun a -> f a k);;
- let rec tree_monadize (f : 'a -> ('
b, 'r) continuation) (t : 'a tree) : ('b tree, 'r
) continuation =
+ let rec tree_monadize (f : 'a -> ('
r,'b) continuation) (t : 'a tree) : ('r,'b tree
) continuation =
match t with
| Leaf a -> continuation_bind (f a) (fun b -> continuation_unit (Leaf b))
| Node (l, r) -> continuation_bind (tree_monadize f l) (fun l' ->
match t with
| Leaf a -> continuation_bind (f a) (fun b -> continuation_unit (Leaf b))
| Node (l, r) -> continuation_bind (tree_monadize f l) (fun l' ->
@@
-368,7
+368,7
@@
interesting functions for the first argument of `tree_monadize`:
It's not immediately obvious to us how to simulate the List monadization of the tree using this technique.
We could simulate the tree annotating example by setting the relevant
It's not immediately obvious to us how to simulate the List monadization of the tree using this technique.
We could simulate the tree annotating example by setting the relevant
-type to `(
'a, 'state -> 'result
) continuation`.
+type to `(
store -> 'result, 'a
) continuation`.
Andre Filinsky has proposed that the continuation monad is
able to simulate any other monad (Google for "mother of all monads").
Andre Filinsky has proposed that the continuation monad is
able to simulate any other monad (Google for "mother of all monads").