reformat advanced
[lambda.git] / miscellaneous_lambda_challenges_and_advanced_topics.mdwn
index 511135a..df05c9e 100644 (file)
-1.     How would you define an operation to reverse a list? (Don't peek at the
+[[!toc]]
+
+#Reversing a list#
+
+How would you define an operation to reverse a list? (Don't peek at the
 [[lambda_library]]! Try to figure it out on your own.) Choose whichever
 implementation of list you like. Even then, there are various strategies you
 can use.
 
 
-2.     An advantage of the v3 lists and v3 (aka "Church") numerals is that they
-       have a recursive capacity built into their skeleton. So for many natural
-       operations on them, you won't need to use a fixed point combinator. Why is
-       that an advantage? Well, if you use a fixed point combinator, then the terms
-       you get
-       won't be strongly normalizing: whether their reduction stops at a normal form
-       will depend on what evaluation order you use. Our online [[lambda evaluator]]
-       uses normal-order reduction, so it finds a normal form if there's one to be
-       had. But if you want to build lambda terms in, say, Scheme, and you wanted to
-       roll your own recursion as we've been doing, rather than relying on Scheme's
-       native `let rec` or `define`, then you can't use the fixed-point combinators
-       `Y` or <code>&Theta;</code>. Expressions using them will have non-terminating
-       reductions, with Scheme's eager/call-by-value strategy. There are other
-       fixed-point combinators you can use with Scheme (in the [week 3 notes](/week3/#index7h2) they
-       were <code>Y&prime;</code> and <code>&Theta;&prime;</code>. But even with
-       them, evaluation order still matters: for some (admittedly unusual)
-       evaluation strategies, expressions using them will also be non-terminating.
+#Efficiently extracting tails and predecessors#
 
-       The fixed-point combinators may be the conceptual stars. They are cool and
-       mathematically elegant. But for efficiency and implementation elegance, it's
-       best to know how to do as much as you can without them. (Also, that knowledge
-       could carry over to settings where the fixed point combinators are in
-       principle unavailable.)
+An advantage of the v3 lists and v3 (aka "Church") numerals is that they
+have a recursive capacity built into their skeleton. So for many natural
+operations on them, you won't need to use a fixed point combinator. Why is
+that an advantage? Well, if you use a fixed point combinator, then the terms
+you get
+won't be strongly normalizing: whether their reduction stops at a normal form
+will depend on what evaluation order you use. Our online [[lambda evaluator]]
+uses normal-order reduction, so it finds a normal form if there's one to be
+had. But if you want to build lambda terms in, say, Scheme, and you wanted to
+roll your own recursion as we've been doing, rather than relying on Scheme's
+native `let rec` or `define`, then you can't use the fixed-point combinators
+`Y` or <code>&Theta;</code>. Expressions using them will have non-terminating
+reductions, with Scheme's eager/call-by-value strategy. There are other
+fixed-point combinators you can use with Scheme (in the [week 3 notes](/week3/#index7h2) they
+were <code>Y&prime;</code> and <code>&Theta;&prime;</code>. But even with
+them, evaluation order still matters: for some (admittedly unusual)
+evaluation strategies, expressions using them will also be non-terminating.
 
-       This is why the v3 lists and numbers are so lovely. However, one disadvantage
-       to them is that it's relatively inefficient to extract a list's tail, or get a
-       number's predecessor. To get the tail of the list `[a;b;c;d;e]`, one will
-       basically be performing some operation that builds up the tail afresh: at
-       different stages, one will have built up `[e]`, then `[d;e]`, then `[c;d;e]`, and
-       finally `[b;c;d;e]`. With short lists, this is no problem, but with longer lists
-       it takes longer and longer. And it may waste more of your computer's memory
-       than you'd like. Similarly for obtaining a number's predecessor.
+The fixed-point combinators may be the conceptual stars. They are cool and
+mathematically elegant. But for efficiency and implementation elegance, it's
+best to know how to do as much as you can without them. (Also, that knowledge
+could carry over to settings where the fixed point combinators are in
+principle unavailable.)
 
-       The v1 lists and numbers on the other hand, had the tail and the predecessor
-       right there as an element, easy for the taking. The problem was just that the
-       v1 lists and numbers didn't have recursive capacity built into them, in the
-       way the v3 implementations do.
+This is why the v3 lists and numbers are so lovely. However, one disadvantage
+to them is that it's relatively inefficient to extract a list's tail, or get a
+number's predecessor. To get the tail of the list `[a;b;c;d;e]`, one will
+basically be performing some operation that builds up the tail afresh: at
+different stages, one will have built up `[e]`, then `[d;e]`, then `[c;d;e]`, and
+finally `[b;c;d;e]`. With short lists, this is no problem, but with longer lists
+it takes longer and longer. And it may waste more of your computer's memory
+than you'd like. Similarly for obtaining a number's predecessor.
 
-       A clever approach would marry these two strategies.
+The v1 lists and numbers on the other hand, had the tail and the predecessor
+right there as an element, easy for the taking. The problem was just that the
+v1 lists and numbers didn't have recursive capacity built into them, in the
+way the v3 implementations do.
 
-       Version 3 makes the list `[a;b;c;d;e]` look like this:
+A clever approach would marry these two strategies.
 
-               \f z. f a (f b (f c (f d (f e z))))
+Version 3 makes the list `[a;b;c;d;e]` look like this:
 
-       or in other words:
+       \f z. f a (f b (f c (f d (f e z))))
 
-               \f z. f a <the result of folding f and z over the tail>
+or in other words:
 
-       Instead we could make it look like this:
+       \f z. f a <the result of folding f and z over the tail>
 
-               \f z. f a <the tail itself> <the result of folding f and z over the tail>
+Instead we could make it look like this:
 
-       That is, now `f` is a function expecting *three* arguments: the head of the
-       current list, the tail of the current list, and the result of continuing to
-       fold `f` over the tail, with a given base value `z`.
+       \f z. f a <the tail itself> <the result of folding f and z over the tail>
 
-       Call this a **version 4** list. The empty list can be the same as in v3:
+That is, now `f` is a function expecting *three* arguments: the head of the
+current list, the tail of the current list, and the result of continuing to
+fold `f` over the tail, with a given base value `z`.
 
-       <pre><code>empty &equiv; \f z. z</code></pre>
+Call this a **version 4** list. The empty list can be the same as in v3:
 
-       The list constructor would be:
-
-       <pre><code>make_list &equiv; \h t. \f z. f h t (t f z)</code></pre>
-
-       It differs from the version 3 `make_list` only in adding the extra argument
-       `t` to the new, outer application of `f`.
-
-       Similarly, `five` as a v3 or Church numeral looks like this:
-
-               \s z. s (s (s (s (s z))))
-
-       or in other words:
+<pre><code>empty &equiv; \f z. z</code></pre>
 
-               \s z. s <the result of applying s to z (pred 5)-many times>
-
-       Instead we could make it look like this:
+The list constructor would be:
 
-               \s z. s <pred 5> <the result of applying s to z (pred 5)-many times>
-
-       That is, now `s` is a function expecting *two* arguments: the predecessor of the
-       current number, and the result of continuing to apply `s` to the base value `z`
-       predecessor-many times.
-
-       Jim had the pleasure of "inventing" these implementations himself. However,
-       unsurprisingly, he wasn't the first to do so. See for example [Oleg's report
-       on P-numerals](http://okmij.org/ftp/Computation/lambda-calc.html#p-numerals).
-
-
-
-3.     **Sets**
-
-       You're now already in a position to implement sets: that is, collections with
-       no intrinsic order where elements can occur at most once. Like lists, we'll
-       understand the basic set structures to be *type-homogenous*. So you might have
-       a set of integers, or you might have a set of pairs of integers, but you
-       wouldn't have a set that mixed both types of elements. Something *like* the
-       last option is also achievable, but it's more difficult, and we won't pursue it
-       now. In fact, we won't talk about sets of pairs, either. We'll just talk about
-       sets of integers. The same techniques we discuss here could also be applied to
-       sets of pairs of integers, or sets of triples of booleans, or sets of pairs
-       whose first elements are booleans, and whose second elements are triples of
-       integers. And so on.
-
-       (You're also now in a position to implement *multi*sets: that is, collections
-       with no intrinsic order where elements can occur multiple times: the multiset
-       {a,a} is distinct from the multiset {a}. But we'll leave these as an exercise.)
-
-       The easiest way to implement sets of integers would just be to use lists. When
-       you "add" a member to a set, you'd get back a list that was either identical to
-       the original list, if the added member already was present in it, or consisted
-       of a new list with the added member prepended to the old list. That is:
-
-               let empty_set = empty  in
-               ; see the library for definitions of any and eq
-               let make_set = \new_member old_set. any (eq new_member) old_set
-                                                       ; if any element in old_set was eq new_member
-                                                       old_set
-                                                       ; else
-                                                       make_list new_member old_set
-
-       Think about how you'd implement operations like `set_union`,
-       `set_intersection`, and `set_difference` with this implementation of sets.
-
-       The implementation just described works, and it's the simplest to code.
-       However, it's pretty inefficient. If you had a 100-member set, and you wanted
-       to create a set which had all those 100-members and some possibly new element
-       `e`, you might need to check all 100 members to see if they're equal to `e`
-       before concluding they're not, and returning the new list. And comparing for
-       numeric equality is a moderately expensive operation, in the first place.
+<pre><code>make_list &equiv; \h t. \f z. f h t (t f z)</code></pre>
+
+It differs from the version 3 `make_list` only in adding the extra argument
+`t` to the new, outer application of `f`.
+
+Similarly, `five` as a v3 or Church numeral looks like this:
+
+       \s z. s (s (s (s (s z))))
 
-       (You might say, well, what's the harm in just prepending `e` to the list even
-       if it already occurs later in the list. The answer is, if you don't keep track
-       of things like this, it will likely mess up your implementations of
-       `set_difference` and so on. You'll have to do the book-keeping for duplicates
-       at some point in your code. It goes much more smoothly if you plan this from
-       the very beginning.)
+or in other words:
 
-       How might we make the implementation more efficient? Well, the *semantics* of
-       sets says that they have no intrinsic order. That means, there's no difference
-       between the set {a,b} and the set {b,a}; whereas there is a difference between
-       the *list* `[a;b]` and the list `[b;a]`. But this semantic point can be respected
-       even if we *implement* sets with something ordered, like list---as we're
-       already doing. And we might *exploit* the intrinsic order of lists to make our
-       implementation of sets more efficient.
-
-       What we could do is arrange it so that a list that implements a set always
-       keeps in elements in some specified order. To do this, there'd have *to be*
-       some way to order its elements. Since we're talking now about sets of numbers,
-       that's easy. (If we were talking about sets of pairs of numbers, we'd use
-       "lexicographic" ordering, where `(a,b) < (c,d)` iff `a < c or (a == c and b <
-       d)`.)
+       \s z. s <the result of applying s to z (pred 5)-many times>
 
-       So, if we were searching the list that implements some set to see if the number
-       `5` belonged to it, once we get to elements in the list that are larger than `5`,
-       we can stop. If we haven't found `5` already, we know it's not in the rest of the
-       list either.
-
-       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
-       implements the set, if it belonged to the set at all. Or that it fell in the
-       right half, it it belonged to the set at all. And then the same sort of
-       determination could be made for whichever half you were directed to. And then
-       for whichever quarter you were directed to next. And so on. Until you either
-       found the element or exhausted the structure and could then conclude that the
-       element in question was not part of the set. These sorts of structures are done
-       using **binary trees** (see below).
-
-
-4.     **Aborting a search through a list**
-
-       We said that the sorted-list implementation of a set was more efficient than
-       the unsorted-list implementation, because as you were searching through the
-       list, you could come to a point where you knew the element wasn't going to be
-       found. So you wouldn't have to continue the search.
-
-       If your implementation of lists was, say v1 lists plus the Y-combinator, then
-       this is exactly right. When you get to a point where you know the answer, you
-       can just deliver that answer, and not branch into any further recursion. If
-       you've got the right evaluation strategy in place, everything will work out
-       fine.
-
-       But what if you're using v3 lists? What options would you have then for
-       aborting a search?
-
-       Well, suppose we're searching through the list `[5;4;3;2;1]` to see if it
-       contains the number `3`. The expression which represents this search would have
-       something like the following form:
-
-               ..................<eq? 1 3>  ~~>
-               .................. false     ~~>
-               .............<eq? 2 3>       ~~>
-               ............. false          ~~>
-               .........<eq? 3 3>           ~~>
-               ......... true               ~~>
-               ?
-
-       Of course, whether those reductions actually followed in that order would
-       depend on what reduction strategy was in place. But the result of folding the
-       search function over the part of the list whose head is `3` and whose tail is `[2;
-       1]` will *semantically* depend on the result of applying that function to the
-       more rightmost pieces of the list, too, regardless of what order the reduction
-       is computed by. Conceptually, it will be easiest if we think of the reduction
-       happening in the order displayed above.
-
-       Well, once we've found a match between our sought number `3` and some member of
-       the list, we'd like to avoid any further unnecessary computations and just
-       deliver the answer `true` as "quickly" or directly as possible to the larger
-       computation in which the search was embedded.
-
-       With a Y-combinator based search, as we said, we could do this by just not
-       following a recursion branch.
-
-       But with the v3 lists, the fold is "pre-programmed" to continue over the whole
-       list. There is no way for us to bail out of applying the search function to the
-       parts of the list that have head `4` and head `5`, too.
+Instead we could make it look like this:
 
-       We *can* avoid *some* unneccessary computation. The search function can detect
-       that the result we've accumulated so far during the fold is now `true`, so we
-       don't need to bother comparing `4` or `5` to `3` for equality. That will simplify the
-       computation to some degree, since as we said, numerical comparison in the
-       system we're working in is moderately expensive.
-
-       However, we're still going to have to traverse the remainder of the list. That
-       `true` result will have to be passed along all the way to the leftmost head of
-       the list. Only then can we deliver it to the larger computation in which the
-       search was embedded.
-
-       It would be better if there were some way to "abort" the list traversal. If,
-       having found the element we're looking for (or having determined that the
-       element isn't going to be found), we could just immediately stop traversing the
-       list with our answer. **Continuations** will turn out to let us do that.
+       \s z. s <pred 5> <the result of applying s to z (pred 5)-many times>
 
-       We won't try yet to fully exploit the terrible power of continuations. But
-       there's a way that we can gain their benefits here locally, without yet having
-       a fully general machinery or understanding of what's going on.
+That is, now `s` is a function expecting *two* arguments: the predecessor of the
+current number, and the result of continuing to apply `s` to the base value `z`
+predecessor-many times.
 
-       The key is to recall how our implementations of booleans and pairs worked.
-       Remember that with pairs, we supply the pair "handler" to the pair as *an
-       argument*, rather than the other way around:
+Jim had the pleasure of "inventing" these implementations himself. However,
+unsurprisingly, he wasn't the first to do so. See for example [Oleg's report
+on P-numerals](http://okmij.org/ftp/Computation/lambda-calc.html#p-numerals).
 
-               pair (\x y. add x y)
 
-       or:
 
-               pair (\x y. x)
+#Sets#
+
+You're now already in a position to implement sets: that is, collections with
+no intrinsic order where elements can occur at most once. Like lists, we'll
+understand the basic set structures to be *type-homogenous*. So you might have
+a set of integers, or you might have a set of pairs of integers, but you
+wouldn't have a set that mixed both types of elements. Something *like* the
+last option is also achievable, but it's more difficult, and we won't pursue it
+now. In fact, we won't talk about sets of pairs, either. We'll just talk about
+sets of integers. The same techniques we discuss here could also be applied to
+sets of pairs of integers, or sets of triples of booleans, or sets of pairs
+whose first elements are booleans, and whose second elements are triples of
+integers. And so on.
+
+(You're also now in a position to implement *multi*sets: that is, collections
+with no intrinsic order where elements can occur multiple times: the multiset
+{a,a} is distinct from the multiset {a}. But we'll leave these as an exercise.)
+
+The easiest way to implement sets of integers would just be to use lists. When
+you "add" a member to a set, you'd get back a list that was either identical to
+the original list, if the added member already was present in it, or consisted
+of a new list with the added member prepended to the old list. That is:
+
+       let empty_set = empty  in
+       ; see the library for definitions of any and eq
+       let make_set = \new_member old_set. any (eq new_member) old_set
+                                               ; if any element in old_set was eq new_member
+                                               old_set
+                                               ; else
+                                               make_list new_member old_set
+
+Think about how you'd implement operations like `set_union`,
+`set_intersection`, and `set_difference` with this implementation of sets.
+
+The implementation just described works, and it's the simplest to code.
+However, it's pretty inefficient. If you had a 100-member set, and you wanted
+to create a set which had all those 100-members and some possibly new element
+`e`, you might need to check all 100 members to see if they're equal to `e`
+before concluding they're not, and returning the new list. And comparing for
+numeric equality is a moderately expensive operation, in the first place.
+
+(You might say, well, what's the harm in just prepending `e` to the list even
+if it already occurs later in the list. The answer is, if you don't keep track
+of things like this, it will likely mess up your implementations of
+`set_difference` and so on. You'll have to do the book-keeping for duplicates
+at some point in your code. It goes much more smoothly if you plan this from
+the very beginning.)
 
-       to get the first element of the pair. Of course you can lift that if you want:
+How might we make the implementation more efficient? Well, the *semantics* of
+sets says that they have no intrinsic order. That means, there's no difference
+between the set {a,b} and the set {b,a}; whereas there is a difference between
+the *list* `[a;b]` and the list `[b;a]`. But this semantic point can be respected
+even if we *implement* sets with something ordered, like list---as we're
+already doing. And we might *exploit* the intrinsic order of lists to make our
+implementation of sets more efficient.
+
+What we could do is arrange it so that a list that implements a set always
+keeps in elements in some specified order. To do this, there'd have *to be*
+some way to order its elements. Since we're talking now about sets of numbers,
+that's easy. (If we were talking about sets of pairs of numbers, we'd use
+"lexicographic" ordering, where `(a,b) < (c,d)` iff `a < c or (a == c and b <
+d)`.)
 
-       <pre><code>extract_fst &equiv; \pair. pair (\x y. x)</code></pre>
+So, if we were searching the list that implements some set to see if the number
+`5` belonged to it, once we get to elements in the list that are larger than `5`,
+we can stop. If we haven't found `5` already, we know it's not in the rest of the
+list either.
+
+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
+implements the set, if it belonged to the set at all. Or that it fell in the
+right half, it it belonged to the set at all. And then the same sort of
+determination could be made for whichever half you were directed to. And then
+for whichever quarter you were directed to next. And so on. Until you either
+found the element or exhausted the structure and could then conclude that the
+element in question was not part of the set. These sorts of structures are done
+using **binary trees** (see below).
+
+
+#Aborting a search through a list#
+
+We said that the sorted-list implementation of a set was more efficient than
+the unsorted-list implementation, because as you were searching through the
+list, you could come to a point where you knew the element wasn't going to be
+found. So you wouldn't have to continue the search.
+
+If your implementation of lists was, say v1 lists plus the Y-combinator, then
+this is exactly right. When you get to a point where you know the answer, you
+can just deliver that answer, and not branch into any further recursion. If
+you've got the right evaluation strategy in place, everything will work out
+fine.
+
+But what if you're using v3 lists? What options would you have then for
+aborting a search?
+
+Well, suppose we're searching through the list `[5;4;3;2;1]` to see if it
+contains the number `3`. The expression which represents this search would have
+something like the following form:
+
+       ..................<eq? 1 3>  ~~>
+       .................. false     ~~>
+       .............<eq? 2 3>       ~~>
+       ............. false          ~~>
+       .........<eq? 3 3>           ~~>
+       ......... true               ~~>
+       ?
+
+Of course, whether those reductions actually followed in that order would
+depend on what reduction strategy was in place. But the result of folding the
+search function over the part of the list whose head is `3` and whose tail is `[2;
+1]` will *semantically* depend on the result of applying that function to the
+more rightmost pieces of the list, too, regardless of what order the reduction
+is computed by. Conceptually, it will be easiest if we think of the reduction
+happening in the order displayed above.
+
+Well, once we've found a match between our sought number `3` and some member of
+the list, we'd like to avoid any further unnecessary computations and just
+deliver the answer `true` as "quickly" or directly as possible to the larger
+computation in which the search was embedded.
+
+With a Y-combinator based search, as we said, we could do this by just not
+following a recursion branch.
+
+But with the v3 lists, the fold is "pre-programmed" to continue over the whole
+list. There is no way for us to bail out of applying the search function to the
+parts of the list that have head `4` and head `5`, too.
 
-       but at a lower level, the pair is still accepting its handler as an argument,
-       rather than the handler taking the pair as an argument. (The handler gets *the
-       pair's elements*, not the pair itself, as arguments.)
+We *can* avoid *some* unneccessary computation. The search function can detect
+that the result we've accumulated so far during the fold is now `true`, so we
+don't need to bother comparing `4` or `5` to `3` for equality. That will simplify the
+computation to some degree, since as we said, numerical comparison in the
+system we're working in is moderately expensive.
+
+However, we're still going to have to traverse the remainder of the list. That
+`true` result will have to be passed along all the way to the leftmost head of
+the list. Only then can we deliver it to the larger computation in which the
+search was embedded.
+
+It would be better if there were some way to "abort" the list traversal. If,
+having found the element we're looking for (or having determined that the
+element isn't going to be found), we could just immediately stop traversing the
+list with our answer. **Continuations** will turn out to let us do that.
 
-       >       *Terminology*: we'll try to use names of the form `get_foo` for handlers, and
-       names of the form `extract_foo` for lifted versions of them, that accept the
-       lists (or whatever data structure we're working with) as arguments. But we may
-       sometimes forget.
+We won't try yet to fully exploit the terrible power of continuations. But
+there's a way that we can gain their benefits here locally, without yet having
+a fully general machinery or understanding of what's going on.
 
-       The v2 implementation of lists followed a similar strategy:
+The key is to recall how our implementations of booleans and pairs worked.
+Remember that with pairs, we supply the pair "handler" to the pair as *an
+argument*, rather than the other way around:
 
-               v2list (\h t. do_something_with_h_and_t) result_if_empty
+       pair (\x y. add x y)
 
-       If the `v2list` here is not empty, then this will reduce to the result of
-       supplying the list's head and tail to the handler `(\h t.
-       do_something_with_h_and_t)`.
+or:
 
-       Now, what we've been imagining ourselves doing with the search through the v3
-       list is something like this:
+       pair (\x y. x)
 
+to get the first element of the pair. Of course you can lift that if you want:
 
-               larger_computation (search_through_the_list_for_3) other_arguments
+<pre><code>extract_fst &equiv; \pair. pair (\x y. x)</code></pre>
 
-       That is, the result of our search is supplied as an argument (perhaps together
-       with other arguments) to the "larger computation". Without knowing the
-       evaluation order/reduction strategy, we can't say whether the search is
-       evaluated before or after it's substituted into the larger computation. But
-       semantically, the search is the argument and the larger computation is the
-       function to which it's supplied.
+but at a lower level, the pair is still accepting its handler as an argument,
+rather than the handler taking the pair as an argument. (The handler gets *the
+pair's elements*, not the pair itself, as arguments.)
 
-       What if, instead, we did the same kind of thing we did with pairs and v2
-       lists? That is, what if we made the larger computation a "handler" that we
-       passed as an argument to the search?
+>      *Terminology*: we'll try to use names of the form `get_foo` for handlers, and
+names of the form `extract_foo` for lifted versions of them, that accept the
+lists (or whatever data structure we're working with) as arguments. But we may
+sometimes forget.
 
-               the_search (\search_result. larger_computation search_result other_arguments)
+The v2 implementation of lists followed a similar strategy:
 
-       What's the advantage of that, you say. Other than to show off how cleverly
-       you can lift.
+       v2list (\h t. do_something_with_h_and_t) result_if_empty
 
-       Well, think about it. Think about the difficulty we were having aborting the
-       search. Does this switch-around offer us anything useful?
+If the `v2list` here is not empty, then this will reduce to the result of
+supplying the list's head and tail to the handler `(\h t.
+do_something_with_h_and_t)`.
 
-       It could.
+Now, what we've been imagining ourselves doing with the search through the v3
+list is something like this:
 
-       What if the way we implemented the search procedure looked something like this?
 
-       At a given stage in the search, we wouldn't just apply some function `f` to the
-       head at this stage and the result accumulated so far (from folding the same
-       function, and a base value, to the tail at this stage)...and then pass the result
-       of that application to the embedding, more leftward computation.
+       larger_computation (search_through_the_list_for_3) other_arguments
 
-       We'd *instead* give `f` a "handler" that expects the result of the current
-       stage *as an argument*, and then evaluates to what you'd get by passing that
-       result leftwards up the list, as before. 
+That is, the result of our search is supplied as an argument (perhaps together
+with other arguments) to the "larger computation". Without knowing the
+evaluation order/reduction strategy, we can't say whether the search is
+evaluated before or after it's substituted into the larger computation. But
+semantically, the search is the argument and the larger computation is the
+function to which it's supplied.
 
-       Why would we do that, you say? Just more flamboyant lifting?
+What if, instead, we did the same kind of thing we did with pairs and v2
+lists? That is, what if we made the larger computation a "handler" that we
+passed as an argument to the search?
 
-       Well, no, there's a real point here. If we give the function a "handler" that
-       encodes the normal continuation of the fold leftwards through the list, we can
-       also give it other "handlers" too. For example, we can also give it the underlined handler:
+       the_search (\search_result. larger_computation search_result other_arguments)
 
+What's the advantage of that, you say. Other than to show off how cleverly
+you can lift.
 
-               the_search (\search_result. larger_computation search_result other_arguments)
-                                  ------------------------------------------------------------------
+Well, think about it. Think about the difficulty we were having aborting the
+search. Does this switch-around offer us anything useful?
 
-       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.)
+It could.
 
-       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.
+What if the way we implemented the search procedure looked something like this?
 
-       In broad outline, a single stage of the search would look like before, except
-       now f would receive two extra, "handler" arguments.
+At a given stage in the search, we wouldn't just apply some function `f` to the
+head at this stage and the result accumulated so far (from folding the same
+function, and a base value, to the tail at this stage)...and then pass the result
+of that application to the embedding, more leftward computation.
 
-               f 3 <result of folding f and z over [2; 1]> <handler to continue folding leftwards> <handler to abort the traversal>
+We'd *instead* give `f` a "handler" that expects the result of the current
+stage *as an argument*, and then evaluates to what you'd get by passing that
+result leftwards up the list, as before. 
 
-       `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.
+Why would we do that, you say? Just more flamboyant lifting?
 
-       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.
+Well, no, there's a real point here. If we give the function a "handler" that
+encodes the normal continuation of the fold leftwards through the list, we can
+also give it other "handlers" too. For example, we can also give it the underlined handler:
 
-       A **version 5** list encodes the kind of fold operation we're envisaging here, in
-       the same way that v3 (and v4) lists encoded the simpler fold operation.
-       Roughly, the list `[5;4;3;2;1]` would look like this:
 
+       the_search (\search_result. larger_computation search_result other_arguments)
+                          ------------------------------------------------------------------
 
-               \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
+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.
 
-               ; or, expanding the fold over [4;3;2;1]:
+A **version 5** list encodes the kind of fold operation we're envisaging here, in
+the same way that v3 (and v4) 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.
-                       (\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)
+
+       \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:
 
-               ; 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
+                       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
-                               ; here's our f
-                               (\hd sofar continue_handler abort_handler. continue_handler hd)
-                               ; here's our z
+                               (\hd sofar continue_handler abort_handler. abort_handler hd)
                                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
+                               larger_computation
 
-       These functions are used like this:
+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.
 
-               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`.
+#Implementing trees#
 
-       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.
+In [[Assignment3]] we proposed a very ad-hoc-ish implementation of trees.
 
-       <!-- (Silly [cultural reference](http://www.newgrounds.com/portal/view/33440).) -->
+Think about how you'd implement them in a more principled way. You could
+use any of the version 1 -- version 5 implementation of lists as a model.
 
-       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).
+To keep things simple, we'll stick to binary trees. A node will either be a
+*leaf* of the tree, or it will have exactly two children.
 
-       *Comments*:
+There are two kinds of trees to think about. In one sort of tree, it's only
+the tree's leaves that are labeled:
 
-       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.
+               .
+          / \ 
+         .   3
+        / \
+       1   2 
 
-       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.
+Linguists often use trees of this sort. The inner, non-leaf nodes of the
+tree do have associated values. But what values they are can be determined from
+the structure of the tree and the values of the node's left and right children.
+So the inner node doesn't need its own independent label.
 
-               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
+In another sort of tree, the tree's inner nodes are also labeled:
+
+               4
+          / \ 
+         2   5
+        / \
+       1   3 
+
+When you want to efficiently arrange an ordered collection, so that it's
+easy to do a binary search through it, this is the way you usually structure
+your data.
+
+These latter sorts of trees can helpfully be thought of as ones where
+*only* the inner nodes are labeled. Leaves can be thought of as special,
+dead-end branches with no label:
+
+                  .4.
+                 /   \ 
+                2     5
+               / \   / \
+          1   3  x x
+         / \ / \
+        x  x x  x
+
+In our earlier discussion of lists, we said they could be thought of as
+data structures of the form:
+
+       Empty_list | Non_empty_list (its_head, its_tail)
+
+And that could in turn be implemented in v2 form as:
+
+       the_list (\head tail. non_empty_handler) empty_handler
+
+Similarly, the leaf-labeled tree:
+
+               .
+          / \ 
+         .   3
+        / \
+       1   2 
+
+can be thought of as a data structure of the form:
+
+       Leaf (its_label) | Non_leaf (its_left_subtree, its_right_subtree)
+
+and that could be implemented in v2 form as:
+
+       the_tree (\left right. non_leaf_handler) (\label. leaf_handler)
+
+And the node-labeled tree:
+
+                  .4.
+                 /   \ 
+                2     5
+               / \   / \
+          1   3  x x
+         / \ / \
+        x  x x  x
+
+can be thought of as a data structure of the form:
+
+       Leaf | Non_leaf (its_left_subtree, its_label, its_right_subtree)
+
+and that could be implemented in v2 form as:
+
+       the_tree (\left label right. non_leaf_handler) leaf_result
+
+
+What would correspond to "folding" a function `f` and base value `z` over a
+tree? Well, if it's an empty tree:
+
+       x
+
+we should presumably get back `z`. And if it's a simple, non-empty tree:
+
+         1
+        / \
+       x   x
+
+we should expect something like `f z 1 z`, or `f <result of folding f and z
+over left subtree> label_of_this_node <result of folding f and z over right
+subtree>`. (It's not important what order we say `f` has to take its arguments
+in.)
+
+A v3-style implementation of node-labeled trees, then, might be:
+
+       let empty_tree = \f z. z  in
+       let make_tree = \left label right. \f z. f (left f z) label (right f z)  in
+       ...
+
+Think about how you might implement other tree operations, such as getting
+the label of the root (topmost node) of a tree; extracting the left subtree of
+a node; and so on.
+
+Think about different ways you might implement leaf-labeled trees.
+
+If you had one tree and wanted to make a larger tree out of it, adding in a
+new element, how would you do that?
+
+When using trees to represent linguistic structures, one doesn't have
+latitude about *how* to build a larger tree. The linguistic structure you're
+trying to represent will determine where the new element should be placed, and
+where the previous tree should be placed.
+
+However, when using trees as a computational tool, one usually does have
+latitude about how to structure a larger tree---in the same way that we had the
+freedom to implement our sets with lists whose members were just appended in
+the order we built the set up, or instead with lists whose members were ordered
+numerically.
+
+When building a new tree, one strategy for where to put the new element and
+where to put the existing tree would be to always lean towards a certain side.
+For instance, to add the element `2` to the tree:
+
+         1
+        / \
+       x   x
+
+we might construct the following tree:
+
+         1
+        / \
+       x   2
+          / \
+         x   x
+
+or perhaps we'd do it like this instead:
+
+         2
+        / \
+       x   1
+          / \
+         x   x
+
+However, if we always leaned to the right side in this way, then the tree
+would get deeper and deeper on that side, but never on the left:
+
+         1
+        / \
+       x   2
+          / \
+         x   3
+                / \
+               x   4
+                  / \
+                 x   5
+                        / \
+                       x   x
+
+and that wouldn't be so useful if you were using the tree as an arrangement
+to enable *binary searches* over the elements it holds. For that, you'd prefer
+the tree to be relatively "balanced", like this:
+
+                  .4.
+                 /   \ 
+                2     5
+               / \   / \
+          1   3  x x
+         / \ / \
+        x  x x  x
 
-               now `extract_head` can return the leftmost head directly, using its `abort_handler`:
+Do you have any ideas about how you might efficiently keep the new trees
+you're building pretty "balanced" in this way?
 
-                       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
+This is a large topic in computer science. There's no need for you to learn
+the various strategies that they've developed for doing this. But
+thinking in broad brush-strokes about what strategies might be promising will
+help strengthen your understanding of trees, and useful ways to implement them
+in a purely functional setting like the lambda calculus.
 
-       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
 
-       more...