From 663dd241274261fa15316bc9621eed9b5c71791f Mon Sep 17 00:00:00 2001
From: jim
Date: Tue, 10 Feb 2015 12:37:59 -0500
Subject: [PATCH] fill in answers to 25
---
exercises/_assignment2_answers.mdwn | 52 ++++++++++++++++++++++++++++++++++++-
1 file changed, 51 insertions(+), 1 deletion(-)
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
-------
--
2.11.0