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.