From 6ff495fd9985a3db4df959b5deea75ea525cfef0 Mon Sep 17 00:00:00 2001 From: Jim Pryor Date: Sun, 3 Oct 2010 16:57:50 -0400 Subject: [PATCH 1/1] week4 tweaks Signed-off-by: Jim Pryor --- week4.mdwn | 75 ++++++++++++++++++++++++++++++++------------------------------ 1 file changed, 39 insertions(+), 36 deletions(-) diff --git a/week4.mdwn b/week4.mdwn index b174581d..fae6c462 100644 --- a/week4.mdwn +++ b/week4.mdwn @@ -250,7 +250,7 @@ So, if we were searching the list that implements some set to see if the number we can stop. If we haven't found `5` already, we know it's not in the rest of the list either. -*Comment*: This is an improvement, but it's still a "linear" search through the list. +> *Comment*: This is an improvement, but it's still a "linear" search through the list. There are even more efficient methods, which employ "binary" searching. They'd represent the set in such a way that you could quickly determine whether some element fell in one half, call it the left half, of the structure that @@ -570,38 +570,41 @@ Of course, like everything elegant and exciting in this seminar, [Oleg discusses it in much more detail](http://okmij.org/ftp/Streams.html#enumerator-stream). -*Comments*: - -1. The technique deployed here, and in the v2 lists, and in our implementations - of pairs and booleans, is known as **continuation-passing style** programming. - -2. We're still building the list as a right fold, so in a sense the - application of `f` to the leftmost element `5` is "outermost". However, - this "outermost" application is getting lifted, and passed as a *handler* - to the next right application. Which is in turn getting lifted, and - passed to its next right application, and so on. So if you - trace the evaluation of the `extract_head` function to the list `[5;4;3;2;1]`, - you'll see `1` gets passed as a "this is the head sofar" answer to its - `continue_handler`; then that answer is discarded and `2` is - passed as a "this is the head sofar" answer to *its* `continue_handler`, - 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. - 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 also is left as an exercise. +> *Comments*: + +> 1. The technique deployed here, and in the v2 lists, and in our +> implementations of pairs and booleans, is known as +> **continuation-passing style** programming. + +> 2. We're still building the list as a right fold, so in a sense the +> application of `f` to the leftmost element `5` is "outermost". However, +> this "outermost" application is getting lifted, and passed as a *handler* +> to the next right application. Which is in turn getting lifted, and +> passed to its next right application, and so on. So if you +> trace the evaluation of the `extract_head` function to the list `[5;4;3;2;1]`, +> you'll see `1` gets passed as a "this is the head sofar" answer to its +> `continue_handler`; then that answer is discarded and `2` is +> passed as a "this is the head sofar" answer to *its* `continue_handler`, +> 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. +> 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. + -- 2.11.0