> let left_head = \xs. (xs f I) I err in
> ...
- > Here's another, more straightforward answer. We [[observed before|where?]] that left-folding the `cons` function over a list reverses it. Hence, it is easy to reverse a list defined in terms of its left-fold:
+ > Here's another, more straightforward answer. We [[observed before|/topics/week2_encodings#flipped-cons]] that left-folding the `cons` function over a list reverses it. Hence, it is easy to reverse a list defined in terms of its left-fold:
> let left_empty = \f z. z in ; this the same as for the right-fold encoding of lists
> let flipped_left_cons = \xs x. \f z. xs f (f z x) in ; left-folding supplies arguments in a different order than cons expects
Using the mapping specified in this week's notes, translate the following lambda terms into combinatory logic:
-
-Let's say that for any lambda term T, [T] is the equivalent Combinatory Logic term. Then we define the [.] mapping as follows.
-
- 1. [a] = a
- 2. [(\aX)] = @a[X]
- 3. [(XY)] = ([X][Y])
-
-Wait, what is that @a ... business? Well, that's another operation on (a variable and) a CL expression, that we can define like this:
-
- 4. @aa = I
- 5. @aX = KX if a is not in X
- 6. @a(Xa) = X if a is not in X
- 7. @a(XY) = S(@aX)(@aY)
-
-
-
-
<ol start=19>
<li><code>[\x x] = @x x = I</code>
<li><code>[\x y. x] = @x [\y. x] = @x. (@y x) = @x (Kx) = S (@x K) (@x x) = S (KK) I</code>; in general expressions of this form <code>S(K<i>M</i>)I</code> will behave just like <code><i>M</i></code> for any expression <code><i>M</i></code>