From 2195d0c1fa3c064c7090ac25a95cc61ae67bf616 Mon Sep 17 00:00:00 2001 From: Jim Pryor Date: Sun, 3 Oct 2010 17:10:03 -0400 Subject: [PATCH] week4 tweaks Signed-off-by: Jim Pryor --- week4.mdwn | 27 ++++++++++++++------------- 1 file changed, 14 insertions(+), 13 deletions(-) diff --git a/week4.mdwn b/week4.mdwn index fae6c462..58bd7473 100644 --- a/week4.mdwn +++ b/week4.mdwn @@ -328,7 +328,7 @@ more rightmost pieces of the list, too, regardless of what order the reduction is computed by. Conceptually, it will be easiest if we think of the reduction happening in the order displayed above. -Well, once we've found a match between our sought number `3` and some member of +Once we've found a match between our sought number `3` and some member of the list, we'd like to avoid any further unnecessary computations and just deliver the answer `true` as "quickly" or directly as possible to the larger computation in which the search was embedded. @@ -453,7 +453,7 @@ Do you have the basic idea? Think about how you'd implement it. A good understanding of the v2 lists will give you a helpful model. In broad outline, a single stage of the search would look like before, except -now f would receive two extra, "handler" arguments. +now `f` would receive two extra, "handler" arguments. f 3 @@ -473,9 +473,10 @@ zero. If you didn't abort, you'd need to know what the more rightward elements of the list multiplied to, because that would affect the answer you passed along to the continue-leftwards handler. -A **version 5** list encodes the kind of fold operation we're envisaging here, in -the same way that v3 (and [v4](/advanced/#index1h1)) lists encoded the simpler fold operation. -Roughly, the list `[5;4;3;2;1]` would look like this: +A **version 5** list encodes the kind of fold operation we're envisaging here, +in the same way that v3 (and [v4](/advanced_lambda/#index1h1)) lists encoded +the simpler fold operation. Roughly, the list `[5;4;3;2;1]` would look like +this: \f z continue_leftwards_handler abort_handler. @@ -588,23 +589,23 @@ detail](http://okmij.org/ftp/Streams.html#enumerator-stream). > and so on. All those steps have to be evaluated to finally get the result > that `5` is the outer/leftmost head of the list. That's not an efficient way > to get the leftmost head. -> +> > We could improve this by building lists as left folds when implementing them > as continuation-passing style folds. We'd just replace above: -> -> let make_list = \h t. \f z continue_handler abort_handler. +> +> let make_list = \h t. \f z continue_handler abort_handler. > f h z (\z. t f z continue_handler abort_handler) abort_handler -> +> > now `extract_head` should return the leftmost head directly, using its > `abort_handler`: -> +> > let extract_head = \lst larger_computation. lst > (\hd sofar continue_handler abort_handler. abort_handler hd) > junk > larger_computation > larger_computation -> +> > 3. To extract tails efficiently, too, it'd be nice to fuse the apparatus -> developed in these v5 lists with the ideas from [v4](/advanced/#index1h1) -> lists. But that is left as an exercise. +> developed in these v5 lists with the ideas from +> [v4](/advanced_lambda/#index1h1) lists. But that is left as an exercise. -- 2.11.0