week4 tweaks
authorJim Pryor <profjim@jimpryor.net>
Sun, 3 Oct 2010 20:57:50 +0000 (16:57 -0400)
committerJim Pryor <profjim@jimpryor.net>
Sun, 3 Oct 2010 20:57:50 +0000 (16:57 -0400)
Signed-off-by: Jim Pryor <profjim@jimpryor.net>
week4.mdwn

index b174581..fae6c46 100644 (file)
@@ -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.
 
 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
 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).
 
 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.
+