X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=week4.mdwn;h=b174581d30a1ca0ce3ca8ba61ab5639b473dc0da;hp=fb843462cfda3053bfe8c95651ae56fc72375d85;hb=6131a5f57f675f9dcafcb3a4ec9d3613a0e29726;hpb=e9750f1e80f6bb2ffe5193ea0c1e7abcf4482b61 diff --git a/week4.mdwn b/week4.mdwn index fb843462..b174581d 100644 --- a/week4.mdwn +++ b/week4.mdwn @@ -27,11 +27,13 @@ of `T`, by the reasoning in the previous answer. A: Right: 
let Y = \T. (\x. T (x x)) (\x. T (x x)) in
-Y Y ≡ \T. (\x. T (x x)) (\x. T (x x)) Y
+Y Y
+≡   \T. (\x. T (x x)) (\x. T (x x)) Y
 ~~> (\x. Y (x x)) (\x. Y (x x))
 ~~> Y ((\x. Y (x x)) (\x. Y (x x)))
 ~~> Y (Y ((\x. Y (x x)) (\x. Y (x x))))
-~~> Y (Y (Y (...(Y (Y Y))...)))
+~~> Y (Y (Y (...(Y (Y Y))...))) + #Q: Ouch! Stop hurting my brain.# @@ -248,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. -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 @@ -258,7 +260,7 @@ 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). +using [binary trees](/implementing_trees). #Aborting a search through a list# @@ -274,10 +276,39 @@ 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 +But what if we wanted to use v3 lists instead? + +> Why would we want to do that? The advantage of the v3 lists and v3 (aka +"Church") numerals is that they have their recursive capacity built into their +very bones. 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 Θ. 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 Y′ and +Θ′. But even with them, evaluation order still +matters: for some (admittedly unusual) evaluation strategies, expressions using +them will also be non-terminating. + +> 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.) + + +So again, what if we're using v3 lists? What options would we have then for +aborting a search or list traversal before it runs to completion? + +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: