From: Jim Pryor Date: Mon, 6 Dec 2010 23:58:04 +0000 (-0500) Subject: spawned off 'using contin to solve same fringe' X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=commitdiff_plain;h=2dba81fca7c1d2dcfb4fdff6f55c74c8cf795470;ds=sidebyside spawned off 'using contin to solve same fringe' Signed-off-by: Jim Pryor --- diff --git a/manipulating_trees_with_monads.mdwn b/manipulating_trees_with_monads.mdwn index 47fa6f0d..3247ce62 100644 --- a/manipulating_trees_with_monads.mdwn +++ b/manipulating_trees_with_monads.mdwn @@ -325,7 +325,7 @@ plain `int`, and the continuation `fun _ -> []`. Then given what we've said about `tree_monadize`, what should we expect `tree_monadize (fun a -> fun k -> a :: k a` to do? -In a moment, we'll return to the same-fringe problem. Since the +Soon we'll return to the same-fringe problem. Since the simple but inefficient way to solve it is to map each tree to a list of its leaves, this transformation is on the path to a more efficient solution. We'll just have to figure out how to postpone computing the @@ -373,136 +373,6 @@ We would eventually want to generalize the continuation type to If you want to see how to parameterize the definition of the `tree_monadize` function, so that you don't have to keep rewriting it for each new monad, see [this code](/code/tree_monadize.ml). -Using continuations to solve the same fringe problem ----------------------------------------------------- - -We've seen two solutions to the same fringe problem so far. -The problem, recall, is to take two trees and decide whether they have -the same leaves in the same order. - -
- ta            tb          tc
- .             .           .
-_|__          _|__        _|__
-|  |          |  |        |  |
-1  .          .  3        1  .
-  _|__       _|__           _|__
-  |  |       |  |           |  |
-  2  3       1  2           3  2
-
-let ta = Node (Leaf 1, Node (Leaf 2, Leaf 3));;
-let tb = Node (Node (Leaf 1, Leaf 2), Leaf 3);;
-let tc = Node (Leaf 1, Node (Leaf 3, Leaf 2));;
-
- -So `ta` and `tb` are different trees that have the same fringe, but -`ta` and `tc` are not. - -The simplest solution is to map each tree to a list of its leaves, -then compare the lists. But because we will have computed the entire -fringe before starting the comparison, if the fringes differ in an -early position, we've wasted our time examining the rest of the trees. - -The second solution was to use tree zippers and mutable state to -simulate coroutines (see [[coroutines and aborts]]). In that -solution, we pulled the zipper on the first tree until we found the -next leaf, then stored the zipper structure in the mutable variable -while we turned our attention to the other tree. Because we stopped -as soon as we find the first mismatched leaf, this solution does not -have the flaw just mentioned of the solution that maps both trees to a -list of leaves before beginning comparison. - -Since zippers are just continuations reified, we expect that the -solution in terms of zippers can be reworked using continuations, and -this is indeed the case. Before we can arrive at a solution, however, -we must define a data structure called a stream: - - type 'a stream = End | Next of 'a * (unit -> 'a stream);; - -A stream is like a list in that it contains a series of objects (all -of the same type, here, type `'a`). The first object in the stream -corresponds to the head of a list, which we pair with a stream -representing the rest of a the list. There is a special stream called -`End` that represents a stream that contains no (more) elements, -analogous to the empty list `[]`. - -Actually, we pair each element not with a stream, but with a thunked -stream, that is, a function from the unit type to streams. The idea -is that the next element in the stream is not computed until we forced -the thunk by applying it to the unit: - -
-# let rec make_int_stream i = Next (i, fun () -> make_int_stream (i + 1));;
-val make_int_stream : int -> int stream = 
-# let int_stream = make_int_stream 1;;
-val int_stream : int stream = Next (1, )         (* First element: 1 *)
-# match int_stream with Next (i, rest) -> rest;;      
-- : unit -> int stream =                         (* Rest: a thunk *)
-
-(* Force the thunk to compute the second element *)
-# (match int_stream with Next (i, rest) -> rest) ();;
-- : int stream = Next (2, )      
-
- -You can think of `int_stream` as a functional object that provides -access to an infinite sequence of integers, one at a time. It's as if -we had written `[1;2;...]` where `...` meant "continue indefinitely". - -So, with streams in hand, we need only rewrite our continuation tree -monadizer so that instead of mapping trees to lists, it maps them to -streams. Instead of - - # tree_monadize (fun a k -> a :: k a) t1 (fun t -> []);; - - : int list = [2; 3; 5; 7; 11] - -as above, we have - - # tree_monadize (fun i k -> Next (i, fun () -> k ())) t1 (fun _ -> End);; - - : int stream = Next (2, ) - -We can see the first element in the stream, the first leaf (namely, -2), but in order to see the next, we'll have to force a thunk. - -Then to complete the same-fringe function, we simply convert both -trees into leaf-streams, then compare the streams element by element. -The code is enitrely routine, but for the sake of completeness, here it is: - -
-let rec compare_streams stream1 stream2 =
-    match stream1, stream2 with 
-    | End, End -> true (* Done!  Fringes match. *)
-    | Next (next1, rest1), Next (next2, rest2) when next1 = next2 -> compare_streams (rest1 ()) (rest2 ())
-    | _ -> false;;
-
-let same_fringe t1 t2 =
-  let stream1 = tree_monadize (fun i k -> Next (i, fun () -> k ())) t1 (fun _ -> End) in 
-  let stream2 = tree_monadize (fun i k -> Next (i, fun () -> k ())) t2 (fun _ -> End) in 
-  compare_streams stream1 stream2;;
-
- -Notice the forcing of the thunks in the recursive call to -`compare_streams`. So indeed: - -
-# same_fringe ta tb;;
-- : bool = true
-# same_fringe ta tc;;
-- : bool = false
-
- -Now, this implementation is a bit silly, since in order to convert the -trees to leaf streams, our tree_monadizer function has to visit every -node in the tree. But if we needed to compare each tree to a large -set of other trees, we could arrange to monadize each tree only once, -and then run compare_streams on the monadized trees. - -By the way, what if you have reason to believe that the fringes of -your trees are more likely to differ near the right edge than the left -edge? If we reverse evaluation order in the tree_monadizer function, -as shown above when we replaced leaves with their ordinal position, -then the resulting streams would produce leaves from the right to the -left. - The idea of using continuations to characterize natural language meaning ------------------------------------------------------------------------ diff --git a/using_continuations_to_solve_same_fringe.mdwn b/using_continuations_to_solve_same_fringe.mdwn new file mode 100644 index 00000000..b65add60 --- /dev/null +++ b/using_continuations_to_solve_same_fringe.mdwn @@ -0,0 +1,130 @@ +Using continuations to solve the same fringe problem +---------------------------------------------------- + +We've seen two solutions to the same fringe problem so far. +The problem, recall, is to take two trees and decide whether they have +the same leaves in the same order. + +
+ ta            tb          tc
+ .             .           .
+_|__          _|__        _|__
+|  |          |  |        |  |
+1  .          .  3        1  .
+  _|__       _|__           _|__
+  |  |       |  |           |  |
+  2  3       1  2           3  2
+
+let ta = Node (Leaf 1, Node (Leaf 2, Leaf 3));;
+let tb = Node (Node (Leaf 1, Leaf 2), Leaf 3);;
+let tc = Node (Leaf 1, Node (Leaf 3, Leaf 2));;
+
+ +So `ta` and `tb` are different trees that have the same fringe, but +`ta` and `tc` are not. + +The simplest solution is to map each tree to a list of its leaves, +then compare the lists. But because we will have computed the entire +fringe before starting the comparison, if the fringes differ in an +early position, we've wasted our time examining the rest of the trees. + +The second solution was to use tree zippers and mutable state to +simulate coroutines (see [[coroutines and aborts]]). In that +solution, we pulled the zipper on the first tree until we found the +next leaf, then stored the zipper structure in the mutable variable +while we turned our attention to the other tree. Because we stopped +as soon as we find the first mismatched leaf, this solution does not +have the flaw just mentioned of the solution that maps both trees to a +list of leaves before beginning comparison. + +Since zippers are just continuations reified, we expect that the +solution in terms of zippers can be reworked using continuations, and +this is indeed the case. Before we can arrive at a solution, however, +we must define a data structure called a stream: + + type 'a stream = End | Next of 'a * (unit -> 'a stream);; + +A stream is like a list in that it contains a series of objects (all +of the same type, here, type `'a`). The first object in the stream +corresponds to the head of a list, which we pair with a stream +representing the rest of a the list. There is a special stream called +`End` that represents a stream that contains no (more) elements, +analogous to the empty list `[]`. + +Actually, we pair each element not with a stream, but with a thunked +stream, that is, a function from the unit type to streams. The idea +is that the next element in the stream is not computed until we forced +the thunk by applying it to the unit: + +
+# let rec make_int_stream i = Next (i, fun () -> make_int_stream (i + 1));;
+val make_int_stream : int -> int stream = 
+# let int_stream = make_int_stream 1;;
+val int_stream : int stream = Next (1, )         (* First element: 1 *)
+# match int_stream with Next (i, rest) -> rest;;      
+- : unit -> int stream =                         (* Rest: a thunk *)
+
+(* Force the thunk to compute the second element *)
+# (match int_stream with Next (i, rest) -> rest) ();;
+- : int stream = Next (2, )      
+
+ +You can think of `int_stream` as a functional object that provides +access to an infinite sequence of integers, one at a time. It's as if +we had written `[1;2;...]` where `...` meant "continue indefinitely". + +So, with streams in hand, we need only rewrite our continuation tree +monadizer so that instead of mapping trees to lists, it maps them to +streams. Instead of + + # tree_monadize (fun a k -> a :: k a) t1 (fun t -> []);; + - : int list = [2; 3; 5; 7; 11] + +as above, we have + + # tree_monadize (fun i k -> Next (i, fun () -> k ())) t1 (fun _ -> End);; + - : int stream = Next (2, ) + +We can see the first element in the stream, the first leaf (namely, +2), but in order to see the next, we'll have to force a thunk. + +Then to complete the same-fringe function, we simply convert both +trees into leaf-streams, then compare the streams element by element. +The code is enitrely routine, but for the sake of completeness, here it is: + +
+let rec compare_streams stream1 stream2 =
+    match stream1, stream2 with 
+    | End, End -> true (* Done!  Fringes match. *)
+    | Next (next1, rest1), Next (next2, rest2) when next1 = next2 -> compare_streams (rest1 ()) (rest2 ())
+    | _ -> false;;
+
+let same_fringe t1 t2 =
+  let stream1 = tree_monadize (fun i k -> Next (i, fun () -> k ())) t1 (fun _ -> End) in 
+  let stream2 = tree_monadize (fun i k -> Next (i, fun () -> k ())) t2 (fun _ -> End) in 
+  compare_streams stream1 stream2;;
+
+ +Notice the forcing of the thunks in the recursive call to +`compare_streams`. So indeed: + +
+# same_fringe ta tb;;
+- : bool = true
+# same_fringe ta tc;;
+- : bool = false
+
+ +Now, this implementation is a bit silly, since in order to convert the +trees to leaf streams, our tree_monadizer function has to visit every +node in the tree. But if we needed to compare each tree to a large +set of other trees, we could arrange to monadize each tree only once, +and then run compare_streams on the monadized trees. + +By the way, what if you have reason to believe that the fringes of +your trees are more likely to differ near the right edge than the left +edge? If we reverse evaluation order in the tree_monadizer function, +as shown above when we replaced leaves with their ordinal position, +then the resulting streams would produce leaves from the right to the +left. +