X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=exercises%2Fassignment12.mdwn;h=f2ddbe3ca86422b6b3ccd173c655aa30a442815c;hp=58068c4f8024545334766078a6d8fe05aa26c59d;hb=30e80630a4bdb0ec23dd7098f735b060f6a3de0f;hpb=1f812aceae40b0f6f80a04acc90b2e5194b50591
diff --git a/exercises/assignment12.mdwn b/exercises/assignment12.mdwn
index 58068c4f..f2ddbe3c 100644
--- a/exercises/assignment12.mdwn
+++ b/exercises/assignment12.mdwn
@@ -117,6 +117,7 @@ Here are the beginnings of functions to move from one focused tree to another:
1. Your first assignment is to complete the definitions of `move_botleft` and `move_right_or_up`. (Really it should be `move_right_or_up_..._and_right`.)
+
Having completed that, we can use define a function that enumerates a tree's fringe, step by step, until it's exhausted:
let make_fringe_enumerator (t: 'a tree) =
@@ -192,6 +193,7 @@ Here are the beginnings of functions to move from one focused tree to another:
3. Now we'll talk about another way to implement the `make_fringe_enumerator` function above (and so too the `same_fringe` function which uses it). Notice that the pattern given above is that the `make_fringe_enumerator` creates a `next_leaf` function and an initial state, and each time you want to advance the `next_leaf` by one step, you do so by calling it with the current state. It will return a leaf label plus a modified state, which you can use when you want to call it again and take another step. All of the `next_leaf` function's memory about where it is in the enumeration is contained in the state. If you saved an old state, took three steps, and then called the `next_leaf` function again with the saved old state, it would be back where it was three steps ago. But in fact, the way we use the `next_leaf` function and state above, there is no back-tracking. Neither do we "fork" any of the states and pursue different forward paths. Their progress is deterministic, and fixed independently of anything that `same_fringe` might do. All that's up to `same_fringe` is to take the decision of when (and whether) to take another step forward.
Given that usage pattern, it would be appropriate and convenient to make the `next_leaf` function remember its state itself, in a mutable variable. The client function `same_fringe` doesn't need to do anything with, or even be given access to, this variable. Here's how we might write `make_fringe_enumerator` according to this plan:
+
let make_fringe_enumerator (t: 'a tree) =
(* create a zipper focusing the botleft of t *)
@@ -290,6 +292,7 @@ Here are the beginnings of functions to move from one focused tree to another:
# next2 ();;
- : int option = None
+
## Same-fringe using streams ##
Now we'll describe a different way to create "the little subprograms" that we built above with `make_fringe_enumerator`. This code will make use of a data structure called a "stream". A stream is like a list in that it wraps a series of elements of a single type. It differs from a list in that the tail of the series is left uncomputed until needed. We turn the stream off and on by thunking it, nad by forcing the thunk.
@@ -322,6 +325,7 @@ You can think of `int_stream` as a functional object that provides access to an
Okay, now armed with the idea of a stream, let's use a Scheme version of them to handle the same-fringe problem. This code is taken from . It uses thunks to delay the evaluation of code that computes the tail of a list of a tree's fringe. It also involves passing "the rest of the enumeration of the fringe" as a thunk argument (`tail-thunk` below). Your assignment is to fill in the blanks in the code, **and also to supply comments to the code,** to explain what every significant piece is doing. Don't forget to supply the comments, this is an important part of the assignment.
+
This code uses Scheme's `cond` construct. That works like this;
(cond
@@ -364,6 +368,8 @@ Some other Scheme details or reminders:
+
+
4. Here is the Scheme code handling the same-fringe problem. You should fill in the blanks:
(define (lazy-flatten tree)