From ec585b7635a456924782477db3bc03308740f22d Mon Sep 17 00:00:00 2001 From: Jim Pryor Date: Thu, 16 Sep 2010 21:25:40 -0400 Subject: [PATCH] lists_and_numbers: lists v3 Signed-off-by: Jim Pryor --- lists_and_numbers.mdwn | 38 ++++++++++++++++++++++++++++++++++++++ 1 file changed, 38 insertions(+) diff --git a/lists_and_numbers.mdwn b/lists_and_numbers.mdwn index 8175064f..2f59e263 100644 --- a/lists_and_numbers.mdwn +++ b/lists_and_numbers.mdwn @@ -308,3 +308,41 @@ However, at this point the elegance gives out. The predecessor function is subst However, if on the other hand you do have some experience programming, consider how you might construct a predecessor function for numbers implemented in this way. Using only the resources we've so far discussed. (So you have no general facility for performing recursion, for instance.) + +Lists, version 3 +---------------- + +It's possible to follow the same design for implementing lists, too. To see this, let's first step back and consider some of the more complex things you might do with a list. We don't need to think specifically inside the confines of the lambda calculus right now. These are generanl reflections. + +Assume you have a list of five integers, which I'll write using the OCaml notation: `[1; 2; 3; 4; 5]`. + +Now one thing you might want to do with the list is to double every member. Another thing you might want to do is to increment every number. More generally, given an arbitrary function `f`, uou might want to get the list which is `[f 1; f 2; f 3; f 4; f 5]`. Computer scientists call this **mapping** the function `f` over the list `[1; 2; 3; 4; 5]`. + +Another thing you might want to do with the list is to retrieve every member which is even. Or every member which is prime. Or, given an arbitrary function f, you might want to **filter** the original list to a shorter list containing only those elements `x` for which `f x` evaluates to true. + +These are very basic, frequently-used operations on lists. + +Another operation on lists is a bit harder to get a mental hold of, but is even more fundamental than the two just mentioned. An example of this operation would be if you were to **sum up** the members of the list. What would you do? We'll you'd start with the first element of the list. Actually, for generality, let's say you start with a *seed value*. In this case the seed value can be 0. Then you take the first element of the list and add it to the seed value. Now you have 1. You take the second element of the list, and add it to the result so far. Now you have 3. You take the third element of the list, and add it to the result so far. And so on. + +This general form of operation is known as **folding** an operation---in this case, the addition operation---over the list. Addition is symmetric, so it doesn't matter whether you start at the left side of the list or the right. But we can't in general rely on the operations to be symmetric. So there are two notions. This is the **left-fold** of an operation f over our list `[1; 2; 3; 4; 5]` given a seed value z: + + f (f (f (f (f z 1) 2) 3) 4) 5 + +and this is the **right-fold**: + + f 1 (f 2 (f 3 (f 4 (f 5 z)))) + +Church's proposal for implementing the numbers identified the essential behavior of a number *m* to be applying an arbitary function s to a base value z *m* times. In a similar spirit, we can identify the essential behavior of a list to be folding an arbitrary operation f over the elements of the list and a seed value z. In other words, we could represent the list `[1; 2; 3; 4; 5]` as a function that accepted arbitrary `f` and `z` as arguments, and returned one of the folds above. + +You could do this using either sort of fold, but choosing the right fold gives us an implementation closest to Church's encoding of the numbers. Then we'd define `[1; 2; 3; 4; 5]` to be: + + \f z. f 1 (f 2 (f 3 (f 4 (f 5 z)))) + +Compare Church's definition of the number five: + + \s z. s (s (s (s (s z)))) + +This has real elegance, and it makes it easy to implement a number of primitive list operatioons. For example, checking whether a list implemented in this way is empty is easy. So too is extracting the head of a list known to be non-empty. However, other operations require some ingenuity. Extracting the tail of a list is about as difficult as retrieving the predecessor of a Church number. (This should not be surprising, given how similar in design these implementations are.) + + + -- 2.11.0