The difference is that this new encoding uses a fold function `g` expecting *three* arguments, and the encoding not only passes the current head as a first argument to that function (as before), but *also* passes the current tail as a new middle argument to that function. As before, we continue to pass the result of the fold *applied to* the tail as the last argument.
-With this encoding scheme, each list would be represented by a somewhat more complex function than before. On the other hand, it would now become as easy to query the list's tail as it is to query its head.
+With this encoding scheme, each list would be represented by a somewhat more complex function than before. On the other hand, it would now become as easy to query the list's tail as it is to query its head. Before the refinement, querying the tail of a list required us to *build up* the tail afresh each time we wanted to extract it. Whereas this refinement *saves a copy* of the tail *for direct access*, as a new middle argument to the fold function, when the list is first constructed.
(Oleg discusses making a parallel refinement in the encoding of numbers [here](http://okmij.org/ftp/Computation/lambda-calc.html#p-numerals).)
Let's consider one or two more, that take different, apparently simpler strategies, avoiding the use of folds in the encoding.
+<a id=v4-lists></a>
Isn't the simplest approach just to represent a non-empty list as an *ordered pair* of its head and its tail? In the first week, we mentioned that the fancier functional programming languages like OCaml and Haskell sharply distinguish between lists and tuples. Lists had to be type-homogenous, and their type was insensitive to their length. Tuples on the other hand could be (though needn't be) type-heterogenous, and their own types *were* determined by the number (and order) of the types of their elements. But we don't have types in the Lambda Calculus. (At least, we don't have a *variety* of types.) So maybe in this context we can identify lists with certain tuples, without getting in trouble.
(In fact, as we discuss elsewhere, this is how Scheme also implements its lists.)
This is in fact a formidable obstacle. The present encoding of lists makes some things easier than our (original) right-fold encoding of lists: it's easier to extract the tail, plus the whole system just seems simpler. But the compensating disadvantage is that we don't know how to perform recursive operations on the lists so encoded. At least, not until we work out a general strategy for expressing `letrec` in the Lambda Calculus. With the list encodings we looked at earlier, that "baked" the fold operation into the list's very construction, we didn't need any such general-purpose `letrec`. The natural recursive operations we wanted to perform on lists were already in our reach.
+<a id=v5-lists></a>
Let's consider one more encoding strategy for lists. This will have the same serious shortcoming as the simple encoding we just considered: we won't be able to do recursive operations with it until we have a general-purpose `letrec`. But in other respects it may be improvement on that encoding. That encoding might seem a bit ad hoc. Plus there's that matter of the `???` in our construction of `[]`, where we don't know what it should be. If we proceed a bit differently, it will be easier to see some systematic rationale for our choices.
We've already seen some **enumerations**. These are "data structures" that consist of a fixed, finite number of discrete values. Such as `true` and `false`. Sometimes enumerations are understood to have a meaningful intrinsic order, but that's not important for our purposes here.