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

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

7. Continuing to encode lists in terms of their left-folds, how should we write `head`? This is challenging.

-*Here is a hint*
+*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.)