X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?a=blobdiff_plain;f=using_continuations_to_solve_same_fringe.mdwn;fp=using_continuations_to_solve_same_fringe.mdwn;h=0000000000000000000000000000000000000000;hb=656923cf6fecaa0fc054f965e315ea08ea2df6f3;hp=1c980a4b806474007cf4d5e6467b665e6a78f4e1;hpb=bb166bcf79a82ef90a330faddc2cdecce06394f6;p=lambda.git diff --git a/using_continuations_to_solve_same_fringe.mdwn b/using_continuations_to_solve_same_fringe.mdwn deleted file mode 100644 index 1c980a4b..00000000 --- a/using_continuations_to_solve_same_fringe.mdwn +++ /dev/null @@ -1,133 +0,0 @@ -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 = [fun] -# let int_stream = make_int_stream 1;; -val int_stream : int stream = Next (1, [fun]) (* First element: 1 *) -# match int_stream with Next (i, rest) -> rest;; -- : unit -> int stream = [fun] (* Rest: a thunk *) - -(* Force the thunk to compute the second element *) -# (match int_stream with Next (i, rest) -> rest) ();; -- : int stream = Next (2, [fun]) -- -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,
-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, you might think that 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, so we'd have to traverse -the entire tree at some point. But you'd be wrong: part of what gets -suspended in the thunking of the stream is the computation of the rest -of the monadized tree. Proving this claim requires adding print -statements (or other tracing technology) within the tree monadizer -function. - -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. -