From d7a978d7e10a32f675fa3b98f21b2a8c32c34c1e Mon Sep 17 00:00:00 2001 From: jim Date: Wed, 18 Feb 2015 05:17:40 -0500 Subject: [PATCH] add more anchors --- topics/week3_lists.mdwn | 2 ++ 1 file changed, 2 insertions(+) diff --git a/topics/week3_lists.mdwn b/topics/week3_lists.mdwn index d6f3a3b2..ac4e0f4e 100644 --- a/topics/week3_lists.mdwn +++ b/topics/week3_lists.mdwn @@ -186,6 +186,7 @@ If you're keeping track, we've now seen three different encoding strategies for Let's consider one or two more, that take different, apparently simpler strategies, avoiding the use of folds in the encoding. + 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.) @@ -232,6 +233,7 @@ Now think about how you'd define recursive operations like `length` or `map`, or 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. + 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. -- 2.11.0