edits

[lambda.git] / lists_and_numbers.mdwn

diff --git a/lists_and_numbers.mdwn b/lists_and_numbers.mdwn
index 2f59e26..571ed7b 100644 (file)
--- a/lists_and_numbers.mdwn
+++ b/lists_and_numbers.mdwn
@@ -1,11 +1,13 @@
+[[!toc]]
+

 Building Lists
 ==============
 
 To build a data-structure, you begin by deciding what the data-structure needs to do. When we built booleans, what they needed to do was select between two choices. When we built ordered pairs, what we needed was a way to wrap two elements into the pair, and ways to operate on the wrapped elements, especially a way to extract a specified one of them.
 
 Building Lists
 ==============
 
 To build a data-structure, you begin by deciding what the data-structure needs to do. When we built booleans, what they needed to do was select between two choices. When we built ordered pairs, what we needed was a way to wrap two elements into the pair, and ways to operate on the wrapped elements, especially a way to extract a specified one of them.
 

-Now we're going to try to build lists. First, let's explain what is the difference bwteen a list and a pair.
+Now we're going to try to build lists. First, let's explain what is the difference between a list and a pair.

 
 

-A list can two elements, but it can also have more elements, or fewer. A list can even have zero elements: this is called the empty list. Sometimes this is written `nil`. In Scheme it's also written `'()` and `(list)`, and in OCaml it's written `[]`. Those languages are nice and have list structures pre-built into them. But we're going to build lists ourselves, from scratch.
+A list can have two elements, but it can also have more elements, or fewer. A list can even have zero elements: this is called the empty list. Sometimes this is written `nil`. In Scheme it's also written `'()` and `(list)`, and in OCaml it's written `[]`. Those languages are nice and have list structures pre-built into them. But we're going to build lists ourselves, from scratch.

 
 OK, so a list doesn't have to have two elements, but still, what's the difference between a two-element list and a pair? And the difference between a three-element list and a triple?
 
 
 OK, so a list doesn't have to have two elements, but still, what's the difference between a two-element list and a pair? And the difference between a three-element list and a triple?
 


@@ -25,6 +27,8 @@ The differences are:
 
 We regard two pairs as being of the same type when their corresponding members are of the same type.
 
 
 We regard two pairs as being of the same type when their corresponding members are of the same type.
 

+Some programming languages permit type-heterogenous lists. Some imperative languages further permit a kind of *mutable* list. We'll consider such things later. For now, we regard these as frills. What we're discussing here is just the prototypical, meat-and-potatoes list.
+

 Another difference between lists and pairs:
 
 *      The length of a list is not essential to its type. A two-element list can be of the same type as a three-element list (whose members are of the right type).
 Another difference between lists and pairs:
 
 *      The length of a list is not essential to its type. A two-element list can be of the same type as a three-element list (whose members are of the right type).


@@ -273,10 +277,14 @@ So, for example:
 
 Adding *m* to *n* is a matter of applying the successor function to *n* *m* times. And we know how to apply an arbitrary function s to *n* *m* times: we just give that function s, and the base-value *n*, to *m* as arguments. Because that's what the function we're using to implement *m* *does*. Hence **add** can be defined to be, simply:
 
 
 Adding *m* to *n* is a matter of applying the successor function to *n* *m* times. And we know how to apply an arbitrary function s to *n* *m* times: we just give that function s, and the base-value *n*, to *m* as arguments. Because that's what the function we're using to implement *m* *does*. Hence **add** can be defined to be, simply:
 

-       \m \n. m succ n
+       \m n. m succ n

 
 Isn't that nice?
 
 
 Isn't that nice?
 

+Alternatively, one could do:
+
+       \m n. \s z. m s (n s z)
+

 How would we tell whether a number was 0? Well, look again at the implementations of the first few numbers:
 
 <pre><code>zero &equiv; \s z. s<sup>0</sup> z &equiv; \s z. z
 How would we tell whether a number was 0? Well, look again at the implementations of the first few numbers:
 
 <pre><code>zero &equiv; \s z. s<sup>0</sup> z &equiv; \s z. z


@@ -295,15 +303,21 @@ Perhaps not as elegant as addition, but still decently principled.
 
 Multiplication is even more elegant. Consider that applying an arbitrary function s to a base value z *m &times; n* times is a matter of applying s to z *n* times, and then doing that again, and again, and so on...for *m* repetitions. In other words, it's a matter of applying the function (\z. n s z) to z *m* times. In other words, *m &times; n* can be represented as:
 
 
 Multiplication is even more elegant. Consider that applying an arbitrary function s to a base value z *m &times; n* times is a matter of applying s to z *n* times, and then doing that again, and again, and so on...for *m* repetitions. In other words, it's a matter of applying the function (\z. n s z) to z *m* times. In other words, *m &times; n* can be represented as:
 

-<pre><code>    \s z. m (\z. n s z) z
-~~> \s z. m n s z</code></pre>
+       \s z. m (\z. n s z) z

 
 

-which eta-reduces to:
+which can be eta-reduced to:
+
+       \s. m (n s)
+
+and we might abbreviate that as:
+
+<pre><code>m &#8728; n</code></pre>

 
 

-       m n

 
 Isn't that nice?
 
 
 Isn't that nice?
 

+And if we *apply* `m` to `n` instead of composing it, we get a implementation of exponentiation.
+

 However, at this point the elegance gives out. The predecessor function is substantially more difficult to construct on this implementation. As with all of these operations, there are several ways to do it, but they all take at least a bit of ingenuity. If you're only first learning programming right now, it would be unreasonable to expect you to be able to figure out how to do it.
 
 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.)
 However, at this point the elegance gives out. The predecessor function is substantially more difficult to construct on this implementation. As with all of these operations, there are several ways to do it, but they all take at least a bit of ingenuity. If you're only first learning programming right now, it would be unreasonable to expect you to be able to figure out how to do it.
 
 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.)


@@ -312,11 +326,11 @@ However, if on the other hand you do have some experience programming, consider
 Lists, version 3
 ----------------
 
 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.
+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 general reflections.

 
 Assume you have a list of five integers, which I'll write using the OCaml notation: `[1; 2; 3; 4; 5]`.
 
 
 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]`.
+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`, you 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.
 
 
 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.