author jim Mon, 9 Feb 2015 00:51:41 +0000 (19:51 -0500) committer Linux User Mon, 9 Feb 2015 00:51:41 +0000 (19:51 -0500)

index 602e4ea..86cda04 100644 (file)
@@ -12,7 +12,7 @@ Define a function `dup (n, x)` that creates a list of *n* copies of `x`. Then us

*Here is a hint / solution*

-Consider the list `[a, b, c]`. It will be encoded as `\f z. f (f (f z a) b) c`. We don't know what will be the result of `f z a`, but let's call this `m a`, for some function `m`. We want `f (m a) b` to also be `m a`, and `f (m a) c` to again also be `m a`. So that we get the same result whether we query `[a]`, or `[a, b]`, or `[a, b, c]`, or whatever. We could get the result that `f (m a) b` if `f` were the **K** combinator (`\x y. x)`. But it can't be that easy, because we also need `f z a` to be `m a`, which will have to somehow represent `a`, rather than another head the list might have had, and if `f` were just **K**, then `f z a` would instead be `z`. (And we can't choose a fixed `z` that would be give the right answer for all lists, with varying heads.)
+Consider the list `[a, b, c]`. It will be encoded as `\f z. f (f (f z a) b) c`. We don't know what will be the result of `f z a`, but let's call this `m a`, for some function `m`. We want `f (m a) b` to also be `m a`, and `f (m a) c` to again also be `m a`. So that we get the same result whether we query `[a]`, or `[a, b]`, or `[a, b, c]`, or whatever. We could get the result that `f (m a) b` was `m a` if `f` were the **K** combinator (`\x y. x)`. But it can't be that easy, because we also need `f z a` to be `m a`, which will have to somehow represent `a`, rather than another head the list might have had, and if `f` were just **K**, then `f z a` would instead be `z`. (And we can't choose a fixed `z` that would be give the right answer for all lists, with varying heads.)

Perhaps we can instead have (1) `m a` be a *function* that accepts `b` (and later, `c`) as arguments and ignores them. Whereas (2) `z` is a function that accepts `a` as an argument and doesn't ignore it, but rather uses it to generate `m a`.