From 0ac2d90aac898f1e1d5f90c502d52845c68b5b2a Mon Sep 17 00:00:00 2001 From: jim Date: Sat, 7 Feb 2015 16:47:29 -0500 Subject: [PATCH] bug fixes --- topics/week2_encodings.mdwn | 19 ++++++++++--------- 1 file changed, 10 insertions(+), 9 deletions(-) diff --git a/topics/week2_encodings.mdwn b/topics/week2_encodings.mdwn index 46f15299..38623649 100644 --- a/topics/week2_encodings.mdwn +++ b/topics/week2_encodings.mdwn @@ -69,7 +69,7 @@ in Kapulet syntax: or: - lambda p q. if p then q else q + lambda p q. if p then q else p Given that we know how to express `if ... then ...` in terms of our encoded Booleans, we can represent this easily in the Lambda Calculus as either: @@ -131,7 +131,7 @@ we do recommend you [get Scheme installed on your computer](/how_to_get_the_programming_languages_running_on_your_computer), and [get started learning Scheme](/learning_scheme). It will help you understand the ideas better to experiment with it. -There's also a (slow, bare-bones, but perfectly adequate) version of Scheme available for online use at . +There's also a (slow, bare-bones, but perfectly adequate) version of Scheme available for online use at . (Unfortunately, though, that Scheme implementation will only display the result of `((lambda-and true) false)` as `#`. You won't be able to see if it's the function assigned to `true` or the function assigned to `false`. You'd have to feed that result some more arguments to see how it behaved.) You should also be experimenting with this site's [[lambda evaluator|code/lambda evaluator]]. @@ -204,7 +204,7 @@ That will evaluate to whatever this does: f (10, f (20, f (30, z))) -For example, if we let `f` be `(+)` and `z` be `0`, then it will be `10 + (20 + (30 + 0))` or `60`. Another example, if we let `f` be `(&)` and `z` be `[]`, then `fold_right ((+), []) [10, 20, 30]` will be `10 & (20 & (30 & []))` or `[10, 20, 30]`, the same sequence we began with. +For example, if we let `f` be `(+)` and `z` be `0`, then it will be `10 + (20 + (30 + 0))` or `60`. Another example, if we let `f` be `(&)` and `z` be `[]`, then `fold_right ((&), []) [10, 20, 30]` will be `10 & (20 & (30 & []))` or `[10, 20, 30]`, the same sequence we began with. The other function works like this: @@ -237,14 +237,15 @@ We also saw in seminar how to define `fold_right`. We could do this in Kapulet l letrec fold_right (f, z) xs = case xs of [] then zs; - y & ys then f (y, fold_right (f, z) ys) + y & ys then f (y, fold_right (f, z) ys) + end in fold_right -(In some presentations you may see this with `f` as a curried function of the form `lambda x z. ...` rather than the uncurried form `lambda (x, z). ...` I have here.) +(In some presentations you may see this expecting `f` to be a curried function `lambda x z. ...` rather than the uncurried `lambda (x, z). ...` that I'm expecting here. We will be shifting to the curried form ourselves momentarily.) We suggested in class that these functions were very powerful, and could be deployed to do most everything you might want to do with a list. Given how our strategy for encoding booleans turned out, this ought to suggest to you the idea that *folding is what we fundamentally do* with lists, just as *conditional branching is what we fundamentally do* with booleans. So we can try to encode lists in terms of lambda expressions that will let us perform folds on them. We could try to do this with either right-folds or left-folds. Either is viable. Some things are more natural if you use right-folds, though, so let's do that. -But what should the encoding look like? We don't know *what* function and *what* starting value someone might want to fold over our list! +What should the encoding look like? We don't know *what* function and *what* starting value someone might want to fold over our list! Wait, does that remind you of anything? @@ -254,15 +255,15 @@ Indeed, we'll make our encoded lists consist of higher-order *functions* that ta \f z. SOMETHING -but what should the `SOMETHING` be? Well, when we supply an `f` and a `z` we should get the right-fold of those over `[a, b, c]` back, so the answer should evidently be: +Now, what should the `SOMETHING` be? Well, when we supply an `f` and a `z` we should get back the right-fold of those over `[a, b, c]`, so the answer should evidently be: \f z. f a (f b (f c z)) -Here we work with curried functions, because that's how the Lambda Calculus does things. You wouldn't want to build up a tuple using the mechanisms described above, and then supply f as an argument to that tuple, and so on. That would be a lot of red tape for no benefit. In the Lambda Calculus, it's simpler to just work with curried functions as our natural idiom. +Here we work with curried functions, because that's how the Lambda Calculus does things. You wouldn't want to build up a tuple using the mechanisms described above, and then supply `f` as an argument to that tuple, and so on. That would be a lot of red tape for no benefit. In the Lambda Calculus, it's simpler to just work with curried functions as our natural idiom. So if `[a, b, c]` should be the displayed higher-order function above, what should `[c]` be? Evidently: - \f z. f c z + \f z. f c z Now what should the empty list `[]` be? Think about it... -- 2.11.0