; here's the abort_handler
larger_computation in
let extract_tail = ; left as exercise
- ;; for real efficiency, it'd be nice to fuse the apparatus developed
- ;; in these v5 lists with the ideas from the v4 lists, above
- ;; but that also is left as an exercise
These functions are used like this:
your reach. And once you have followed it, you'll be well on your way to
appreciating the full terrible power of continuations.
-<!-- (Silly [cultural reference](http://www.newgrounds.com/portal/view/33440).) -->
+ <!-- (Silly [cultural reference](http://www.newgrounds.com/portal/view/33440).) -->
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 the v4 lists, above.
+ But that also is left as an exercise.
5. Implementing (self-balancing) trees