(no commit message)

[lambda.git] / topics / week2_encodings.mdwn

diff --git a/topics/week2_encodings.mdwn b/topics/week2_encodings.mdwn
index 290cd5d..091fb4c 100644 (file)
--- a/topics/week2_encodings.mdwn
+++ b/topics/week2_encodings.mdwn
@@ -231,6 +231,7 @@ That will evaluate to whatever this does:
 
     f (f (f (z, 10), 20), 30)
 
 
     f (f (f (z, 10), 20), 30)
 

+<a id=flipped-cons></a>

 With a commutative operator like `(+)`, it makes no difference whether you say `fold_right ((+), z) xs` or `fold_left ((+), z) xs`. But with other operators it will make a difference. We can't say `fold_left ((&), []) [10, 20, 30]`, since that would start by trying to evaluate `[] & 10`, which would crash. But we could do this:
 
     let
 With a commutative operator like `(+)`, it makes no difference whether you say `fold_right ((+), z) xs` or `fold_left ((+), z) xs`. But with other operators it will make a difference. We can't say `fold_left ((&), []) [10, 20, 30]`, since that would start by trying to evaluate `[] & 10`, which would crash. But we could do this:
 
     let


@@ -397,6 +398,8 @@ In fact, there's a way of looking at this that makes it look incredibly natural.
 
     \x. f (g x)
 
 
     \x. f (g x)
 

+For example, the operation that maps a number `n` to <code>n<sup>2</sup>+1</code> is the composition of the successor function and the squaring function (first we square, then we take the successor).
+

 The composition of a function `f` with itself, namely:
 
     \x. f (f x)
 The composition of a function `f` with itself, namely:
 
     \x. f (f x)


@@ -415,13 +418,13 @@ we are proposing to encode it as:
 
 And indeed this is the Church encoding of the numbers:
 
 
 And indeed this is the Church encoding of the numbers:
 

-<code>0 &equiv; \f z. I z &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;;  or \f z. f<sup>0</sup> z</code>  
-<code>1 &equiv; \f z. f z &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;;  or \f z. f<sup>1</sup> z</code>  
-<code>2 &equiv; \f z. f (f z) &nbsp;&nbsp;&nbsp;&nbsp;;  or \f z. f<sup>2</sup> z</code>  
-<code>3 &equiv; \f z. f (f (f z)) ;  or \f z. f<sup>3</sup> z</code>  
+<code>0 &equiv; \f z. z &nbsp;&nbsp;;  <~~> \f z. I z, or \f z. f<sup>0</sup> z</code>  
+<code>1 &equiv; \f z. f z &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;;  or \f z. f<sup>1</sup> z</code>  
+<code>2 &equiv; \f z. f (f z) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;;  or \f z. f<sup>2</sup> z</code>  
+<code>3 &equiv; \f z. f (f (f z)) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;;  or \f z. f<sup>3</sup> z</code>  

 <code>...</code>
 
 <code>...</code>
 

-The encoding for `0` is equivalent to `\f z. z`, which we've also proposed as the encoding for `[]` and for `false`. Don't read too much into this.
+The encoding for `0` is what we also proposed as the encoding for `[]` and for `false`. Don't read too much into this.

 
 Given the above, can you figure out how to define the `succ` function? We already worked through the definition of `cons`, and this is just a simplification of that, so you should be able to do it. We'll make it a homework.
 
 
 Given the above, can you figure out how to define the `succ` function? We already worked through the definition of `cons`, and this is just a simplification of that, so you should be able to do it. We'll make it a homework.