+This "handler" encodes the search's having finished, and delivering a final
+answer to whatever else you wanted your program to do with the result of the
+search. If you like, at any stage in the search you might just give an argument
+to *this* handler, instead of giving an argument to the handler that continues
+the list traversal leftwards. Semantically, this would amount to *aborting* the
+list traversal! (As we've said before, whether the rest of the list traversal
+really gets evaluated will depend on what evaluation order is in place. But
+semantically we'll have avoided it. Our larger computation won't depend on the
+rest of the list traversal having been computed.)
+
+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.
+
+ f 3 <result of folding f and z over [2; 1]> <handler to continue folding leftwards> <handler to abort the traversal>
+
+`f`'s job would be to check whether `3` matches the element we're searching for
+(here also `3`), and if it does, just evaluate to the result of passing `true` to
+the abort handler. If it doesn't, then evaluate to the result of passing
+`false` to the continue-leftwards handler.
+
+In this case, `f` wouldn't need to consult the result of folding `f` and `z` over `[2;
+1]`, since if we had found the element `3` in more rightward positions of the
+list, we'd have called the abort handler and this application of `f` to `3` etc
+would never be needed. However, in other applications the result of folding `f`
+and `z` over the more rightward parts of the list would be needed. Consider if
+you were trying to multiply all the elements of the list, and were going to
+abort (with the result `0`) if you came across any element in the list that was
+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:
+
+
+ \f z continue_leftwards_handler abort_handler.
+ <fold f and z over [4;3;2;1]>
+ (\result_of_fold_over_4321. f 5 result_of_fold_over_4321 continue_leftwards_handler abort_handler)
+ abort_handler
+
+ ; or, expanding the fold over [4;3;2;1]:
+
+ \f z continue_leftwards_handler abort_handler.
+ (\continue_leftwards_handler abort_handler.
+ <fold f and z over [3;2;1]>
+ (\result_of_fold_over_321. f 4 result_of_fold_over_321 continue_leftwards_handler abort_handler)
+ abort_handler
+ )
+ (\result_of_fold_over_4321. f 5 result_of_fold_over_4321 continue_leftwards_handler abort_handler)
+ abort_handler
+
+ ; and so on
+
+Remarks: the `larger_computation` handler should be supplied as both the
+`continue_leftwards_handler` and the `abort_handler` for the leftmost
+application, where the head `5` is supplied to `f`; because the result of this
+application should be passed to the larger computation, whether it's a "fall
+off the left end of the list" result or it's a "I'm finished, possibly early"
+result. The `larger_computation` handler also then gets passed to the next
+rightmost stage, where the head `4` is supplied to `f`, as the `abort_handler` to
+use if that stage decides it has an early answer.
+
+Finally, notice that we don't have the result of applying `f` to `4` etc given as
+an argument to the application of `f` to `5` etc. Instead, we pass
+
+ (\result_of_fold_over_4321. f 5 result_of_fold_over_4321 <one_handler> <another_handler>)
+
+*to* the application of `f` to `4` as its "continue" handler. The application of `f`
+to `4` can decide whether this handler, or the other, "abort" handler, should be
+given an argument and constitute its result.
+
+
+I'll say once again: we're using temporally-loaded vocabulary throughout this,
+but really all we're in a position to mean by that are claims about the result
+of the complex expression semantically depending only on this, not on that. A
+demon evaluator who custom-picked the evaluation order to make things maximally
+bad for you could ensure that all the semantically unnecessary computations got
+evaluated anyway. We don't have any way to prevent that. Later,
+we'll see ways to *semantically guarantee* one evaluation order rather than
+another. Though even then the demonic evaluation-order-chooser could make it
+take unnecessarily long to compute the semantically guaranteed result. Of
+course, in any real computing environment you'll know you're dealing with a
+fixed evaluation order and you'll be able to program efficiently around that.
+
+In detail, then, here's what our v5 lists will look like:
+
+ let empty = \f z continue_handler abort_handler. continue_handler z in
+ let make_list = \h t. \f z continue_handler abort_handler.
+ t f z (\sofar. f h sofar continue_handler abort_handler) abort_handler in
+ let isempty = \lst larger_computation. lst
+ ; here's our f
+ (\hd sofar continue_handler abort_handler. abort_handler false)
+ ; here's our z
+ true
+ ; here's the continue_handler for the leftmost application of f
+ larger_computation
+ ; here's the abort_handler
+ larger_computation in
+ let extract_head = \lst larger_computation. lst
+ ; here's our f
+ (\hd sofar continue_handler abort_handler. continue_handler hd)
+ ; here's our z
+ junk
+ ; here's the continue_handler for the leftmost application of f
+ larger_computation
+ ; here's the abort_handler
+ larger_computation in
+ let extract_tail = ; left as exercise
+
+These functions are used like this:
+
+ let my_list = make_list a (make_list b (make_list c empty) in
+ extract_head my_list larger_computation
+
+If you just want to see `my_list`'s head, the use `I` as the
+`larger_computation`.
+
+What we've done here does take some work to follow. But it should be within
+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).) -->
+
+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.