From: Jim Date: Tue, 10 Feb 2015 22:10:00 +0000 (-0500) Subject: Merge branch 'master' into working X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=commitdiff_plain;h=26c8d6da76887c3756f2ce856b03f490945814c0;hp=e4e1e0f2f5156d78cd2d896d9f3c711babd7ac15 Merge branch 'master' into working * master: fill in answers to 25 expand on Scheme heads #true in r7rs move Real World OCaml add stubs for week3 --- diff --git a/exercises/_assignment2_answers.mdwn b/exercises/_assignment2_answers.mdwn index e131311c..bb3b724f 100644 --- a/exercises/_assignment2_answers.mdwn +++ b/exercises/_assignment2_answers.mdwn @@ -182,8 +182,58 @@ Folds and Lists 25. We mentioned in the Encoding notes that `fold_left (flipped_cons, []) xs` would give us the elements of `xs` but in the reverse order. So that's how we can express `reverse` in terms of `fold_left`. How would you express `reverse` in terms of `fold_right`? As with problem 22, don't use `letrec`! - See the [[hint|assignment2 hint]]. + *Here is a boring, inefficient answer* + let + append (ys, zs) = fold_right ((&), zs) ys; # aka (&&) + f (y, prev) = append (prev, [y]); + reverse xs = fold_right (f, []) xs + in reverse + + or (same basic idea, just written differently): + + let + f (y, prev) = fold_right ((&), [y]) prev; + reverse xs = fold_right (f, []) xs + in reverse + + *Here is an elegant, efficient answer following the [[hint|assignment2 hint]]* + + Suppose the list we want to reverse is `[10, 20, 30]`. Applying `fold_right` to this will begin by computing `f (30, z)` for some `f` and `z` that we specify. If we made the result of that be something like `30 & blah`, or any larger structure that contained something of that form, it's not clear how we could, using just the resources of `fold_right`, reach down into that structure and replace the `blah` with some other element, as we'd evidently need to, since after the next step we should get `30 & (20 & blah)`. What we'd like instead is something like this: + + 30 & < > + + Where `< >` isn't some *value* but rather a *hole*. Then with the next step, we want to plug into that hole `20 & < >`, which contains its own hole. Getting: + + 30 & (20 & < >) + + And so on. That is the key to the solution. The questions you need to answer, to turn this into something executable, are: + + 1. What is a hole? How can we implement it? + + A hole is a bound variable. `30 & < >` is `lambda x. 30 & x`. + + 2. What should `f` be, so that the result of the second step, namely `f (20, 30 & < >)`, is `30 & (20 & < >)`? + + let + f (y, prev) = lambda x. prev (y & x) + in ... + + 3. Given that choice of `f`, what should `z` be, so that the result of the first step, namely `f (30, z)` is `30 & < >`? + + The identity function: `f (30, (lambda y. y))` will reduce to `lambda x. (lambda y. y) (30 & x)`, which will reduce to `lambda x. 30 & x`. + + 4. At the end of the `fold_right`, we're going to end with something like `30 & (20 & (10 & < >))`. But what we want is `[30, 20, 10]`. How can we turn what we've gotten into what we want? + + Supply it with `[]` as an argument. + + 5. So now put it all together, and explain how to express `reverse xs` using `fold_right` and primitive syntax like `lambda`, `&`, and `[]`? + + let + f (y, prev) = lambda x. prev (y & x); + id match lambda y. y; + reverse xs = (fold_right (f, id) xs) [] + in reverse Numbers ------- diff --git a/index.mdwn b/index.mdwn index 7b39b981..5bddb85b 100644 --- a/index.mdwn +++ b/index.mdwn @@ -100,6 +100,16 @@ The [[differences between our made-up language and Scheme, OCaml, and Haskell|ro > We posted [[answers to Week 1's homework|exercises/assignment1_answers]]. +(**Week 3**) Thursday 12 February 2015 +> Topics: +More on Lists (in progress); +Combinatorial Logic (in progress); +Reduction Strategies and Normal Forms (in progress); +Homework (in progress) + +> Also, by this point you should be able to handle all of *The Little Schemer* except for Chapters 9 and 10. Chapter 9 covers what is going on under the hood with `letrec`, and that will be our topic for next week. + + * [Think OCaml](http://greenteapress.com/thinkocaml/thinkocaml.pdf) (142 pp. pdf) - +* [Real World OCaml](https://realworldocaml.org/v1/en/html/index.html) (510 pp. text from 2013) + * recommend reading [Chapters 1-4](https://realworldocaml.org/v1/en/html/a-guided-tour.html) when getting started (Chapter 4 is a bit more advanced) + * then [Chapter 6](https://realworldocaml.org/v1/en/html/variants.html) when learning types + * then [Chapter 8](https://realworldocaml.org/v1/en/html/imperative-programming-1.html) when learning about mutation (OCaml has what we call *explicit* mutation) ### Other ### @@ -64,4 +67,3 @@ * OCaml-Tutorial [Glossary](http://mirror.ocamlcore.org/ocaml-tutorial.org/glossary.html) * [Reddit's r/ocaml](https://www.reddit.com/r/ocaml) * [Stack Overflow](https://stackoverflow.com/questions/tagged/ocaml?sort=faq) questions tagged "ocaml" -* [Real World OCaml](https://realworldocaml.org/v1/en/html/index.html) (510 pp. text from 2013) diff --git a/rosetta1.mdwn b/rosetta1.mdwn index e3534511..1c42a133 100644 --- a/rosetta1.mdwn +++ b/rosetta1.mdwn @@ -78,7 +78,7 @@ These relations are written in Haskell and OCaml as `&&`, `||`, and `not`. (Hask The values that are written `'true` and `'false` in Kapulet are written in Haskell as `True` and `False`, and in OCaml as just `true` and `false`. (It'd be more consistent with OCaml's other naming policies for them to have said True and False, but they didn't.) These are written `#t` and `#f` in Scheme, but in Scheme in many contexts any value that isn't `#f` will behave as though it were `#t`, even values you might think are more "false-like", like `0` and the empty list. Thus `(if 0 'zero 'nope)` will evaluate to `'zero`. -Some Scheme implementations, such as Racket, permit `#true` and `#false` as synonyms for `#t` and `#f`. +Some Scheme implementations, such as Racket, permit `#true` and `#false` as synonyms for `#t` and `#f`. (These aliases are also mandated in "version 7", r7rs, of the Scheme standard.) Scheme also recognizes the values `'true` and `'false`, but it treats `'false` as distinct from `#f`, and thus as a "truth-like" value, like all of its other values that aren't `#f`. Kapulet essentially took Scheme's `boolean` values and collapsed them into being a subtype of its `symbol` values. @@ -110,7 +110,13 @@ Scheme has no infix operators. It ruthlessly demands that all functions to be ap (+ 3 2) -and the like. Moreover, in Scheme parentheses are never optional and never redundant. In contexts like this, the parentheses are necessary to express that the function is being applied; `+ 3 2` on its own is not a complete Scheme expression. And if the `+` were surrounded by its own parentheses, as in: +and the like. Here is an example where the function to be applied is the result of evaluating a more complex expression: + + ((if #t + *) 3 2) + +which will evaluate to `5`, not `6`. + +In Scheme the parentheses are never optional and never redundant. In expressions like `(+ 3 2)`, the parentheses are necessary to express that the function is being applied; `+ 3 2` on its own is not a complete Scheme expression. And if the `+` were surrounded by its own parentheses, as in: ((+) 3 2)