X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=miscellaneous_lambda_challenges_and_advanced_topics.mdwn;h=511135a0ffba3a95bc87a449d778dd87f3ca7253;hp=37f2a1026074ec67becf0d56897a0b04e57b6972;hb=b3781261c60b4d7cbaee3a48449b3319e6b51f31;hpb=08fe47cd79e1dff91bf5c764c103fcb05c1abac2

diff --git a/miscellaneous_lambda_challenges_and_advanced_topics.mdwn b/miscellaneous_lambda_challenges_and_advanced_topics.mdwn
index 37f2a102..511135a0 100644
--- a/miscellaneous_lambda_challenges_and_advanced_topics.mdwn
+++ b/miscellaneous_lambda_challenges_and_advanced_topics.mdwn
@@ -433,9 +433,6 @@ can use.
 				; 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:
 
@@ -449,12 +446,51 @@ can use.
 	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` can return the leftmost head directly, using its `abort_handler`:
+
+			let extract_head = \lst larger_computation. lst
+					; here's our f
+					(\hd sofar continue_handler abort_handler. abort_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
+
+	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