From 204a67a64f802ba126c2744c5bd47bcb7c6af4e9 Mon Sep 17 00:00:00 2001 From: Chris Barker Date: Tue, 7 Dec 2010 13:00:05 -0500 Subject: [PATCH] edit --- assignment9.mdwn | 46 +++++++++++++++++++++++----------------------- 1 file changed, 23 insertions(+), 23 deletions(-) diff --git a/assignment9.mdwn b/assignment9.mdwn index dfc4d475..36a7015f 100644 --- a/assignment9.mdwn +++ b/assignment9.mdwn @@ -32,41 +32,41 @@ 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. This solution is -efficient: the zipper doesn't visit any leaves beyond the first -mismatch. +simulate coroutines (see [[coroutines and aborts]], and [[assignment +8]]). 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. +This solution is efficient: the zipper doesn't visit any leaves beyond +the first mismatch. 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. Your assignment is to show how. -TO-DO LIST for solving the problem ----------------------------------- +The first step is to review your answer to [[assignment8]], and make +sure you understand what is going on. -1. Review the simple but inefficient solution (easy). -2. Understand the zipper/mutable state solution in [[coroutines and aborts]] (harder). -3. Two obvious approaches: +Two strategies for solving the problem +-------------------------------------- -a. Review the list-zipper/list-continuation example given in + +1. Review the list-zipper/list-continuation example given in class in [[from list zippers to continuations]]; then figure out how to re-functionalize the zippers used in the zipper solution. -b. Review how the continuation-flavored tree\_monadizer managed to -map a tree to a list of its leaves, in [[manipulating trees with -monads]]. Spend some time trying to understand exactly what it does: -compute the tree-to-list transformation for a tree with two leaves, -performing all beta reduction by hand using the definitions for -bind\_continuation, unit\_continuation and so on. If you take this -route, study the description of streams (a particular kind of data -structure) below. The goal will be to arrange for the -continuation-flavored tree_monadizer to transform a tree into a stream -instead of into a list. Once you've done that, completing the -same-fringe problem will be easy. +2. Review how the continuation-flavored tree\_monadizer managed to + map a tree to a list of its leaves, in [[manipulating trees with + monads]]. Spend some time trying to understand exactly what it + does: compute the tree-to-list transformation for a tree with two + leaves, performing all beta reduction by hand using the + definitions for bind\_continuation, unit\_continuation and so on. + If you take this route, study the description of streams (a + particular kind of data structure) below. The goal will be to + arrange for the continuation-flavored tree_monadizer to transform + a tree into a stream instead of into a list. Once you've done + that, completing the same-fringe problem will be easy. ------------------------------------- -- 2.11.0