Answers to Problem Set 1
- Yes, they both represent the doubling function ("W plus"). The name of the variable does not matter (but we will usually use "x", "y", "z", "f", "g", or "h").
- It is the application of the doubling function to "5", or in other words, "10".
- It is the function that, given parameter "x", yields the square of "x". This function "x\ sqr x" is the same as just "sqr".
- It is the function that, given parameter "x", yields the square of "x" plus the square of "x". In other words, it yields the double of the square of "x". Given a parameter of, say, "3", it would yield the double of "9", or in other words, "18".
- Since the function takes the double of a square, it could be written as "B dub sqr" (where "dub" is a doubling function), or in other words "B (W plus) sqr".
(The reader may be wondering if this function can be formed
using combinators instead of lambdas; it can, but because
it is a little complicated, we'll delay showing how for a bit.)
(Incidentally, it is a fairly well-known fact of arithmetic that
this function and the function mentioned in problem 2 always yield
the same thing, given the same parameters).
beta-reduces to
and then to
Then we can see that this is the composition of squaring
with succession.
Then, in the new lambda, only the left side is mentioned,
so we can push the lambda left with "C", giving
Then, since "x\ minus x" can be eta-reduced to "minus", we get
We are now left only with one lambda. The only occurence of the "x"
is on the left, so we can push the lambda left with "C":
Now it is just a matter of pushing the lambda right a couple times:
Now, we focus on the next lambda, the one with the "x". Once again,
only the right side mentions "x", so we push right with "B":
Now, we focus on the next lambda, the one with the "g". It can
be gotten rid of immediately using an eta-reduction, leaving
Now, our answer is simply
("Composition composed with composition")
Now, "f" is mentioned on the left ("S f") only, so we rewrite with "C":
This gives us an interesting way of writing the W combinator
in terms of "C", "S", and "I".
This is an interesting combinator which we will call "N". Whereas
"S" was a generalized version of "W", "N" is a more general
form still. From "S"'s rewrite rule,
we see that "S" is like "W" except that it allows the second
"x" to be modified by a function before being passed to the
binary "f". "N", with the rewrite rule,
allows both "x"s to be modified (each by a different function)
before each is passed to the binary "f".
The idea of using a construct like a lambda to refer to functions
began, it seems, with Alonzo Church in the 1930s or so as a device
for his "lambda calculus" (Gottlob Frege I think may have used a similar
notation a bit earlier). Before lambdas were used, functions were
apparently referred to in this sort of way:
This sort of notation requires that the function be given an
arbitrary name "f" (in addition to an arbitrary name "x" for the parameter),
whereas with a lambda construct, a name like "f" is not needed.
There are actually many different notations in use for the lambda
construct. In the most standard notation, the last function would
be written
using " where a backslash ("\") is used in place of the lambda symbol. Also,
in the Haskell programming language,
is used.
We've already introduced several interesting combinators,
including I, B, C, W, K, and S. In this section, we'll introduce
a series of combinators called "iterators". These combinators are
very similar to the natural numbers "0", "1", "2", "3", and so forth.
The first iterator we'll introduce is the one which corresponds
to the number two. This combinator, "2", has the rewrite rule:
This combinator takes a function "f" and yields a function that
applies "f" two times. For instance, "2 sqr" would be a function that
squares a number twice (i.e., raises it to the fourth power); applying
"2 sqr" to a number "3" would give "sqr (sqr 3)", or in other words "81".
"2 sqr" is the same as "B sqr sqr".
Now, we introduce the iterator "3", with the rewrite rule:
This combinator take a function "f" and yields a function that
applies "f" three times. In other words, given "f", it yields
"Bf(Bff)", which is the same as "B(Bff)f". Continuing this pattern, we
define "4" to have the rewrite rule:
Combinators that are like "2", "3", and "4" are called iterators.
In an expression "4f", the "f" is called the iterand, and
the the result is called an iteration of "f".
There are, of course, iterators for the two very special numbers
one and zero. "1" is an iterator that takes a function "f" and yields
a function that applies "f" a single time (in other words, it
makes no change on "f"); it would have the rewrite rule:
In extension, the "1" iterator is the same as the "I" combinator,
since it makes no change to its parameter.
Next, the "0" iterator is a combinator that takes a function "f"
and yields a function that applies "f" no times at all:
In the last section we showed how the I, B, C, W, and K combinators
could be used to form all other combinators. Since an iterator is
a kind of combinator, iterators can also be formed from I, B, C, W, and K.
We already mentioned that the "1" iterator is the same as the
I combinator. The "0" iterator when applied to any function yields
the I combinator, so we can say that
Also, the "2" iterator takes a function "f" and yields "Bff"
(composition of "f" with itself). Because of this, we say that
Now, as for the "3" iterator, it is
And, the "4" iterator is
At this point, it looks like "SB" may be a successor function,
since "SB2" is "3" and "SB3" is "4". In fact, "SB" is a successor
function; it may be useful to write it using lambdas:
It takes three parameters; the first one, "n", is the iterator
to take the successor of. The next one is "f", the function to
iterate. The third is "x", the thing that will have "f" applied
to it some number of times. Then, after taking these three parameters,
"SB" yields, not "nfx" (which would be "f" applied to "x" the original
number of times), but "f(nfx)", which is "f" applied to "x" the
original number of times plus one more time.
We found that "SB" is a successor function, a function that adds one.
We'll now show that "NB" is a general addition function, where
"N" is the combinator such that
If "N" is this combinator, then "NB", the addition function, is
Unlike the successor function which took three parameters, this
function takes four parameters; "m" is the iterator that is being added
(i.e., the amount to add); "n" is the original iterator; "f" is
the function being iterated; and "x" is the thing that "f" will
be applied to some number of times. Unlike the successor function
which gave "f(nfx)" ("f" applied to "x" the original number of
times plus one more), the addition function yields "mf(nfx)"
("f" applied to "x" the original number of times plus "m" more times).
As noted in the last problem, "3(2K)" is the same as "6K". And,
in general, "3(2f)" is the same as "6f". Thus, "B 3 2" is the same as "6".
It seems that the B combinator can be used to multiply iterators,
and it can.
This makes sense because in general, if "m" and "n" are iterators,
then "m(nf)" is a function that applies "nf" "m" times, but "nf"
is the applies "f" "n" times, so "m(nf)" applies "f" a total of "m * n"
times. So, in general, "B m n", given a function "f", yields a
function that applies "f" "m * n" times.
It is interesting that the combinator for multiplication is
even simpler than the combinator for addition.
As demonstrated in the last problem, "3 2" is the cube of "2", or
in other words, "8". In general, if "m" and "n" are iterators,
then "m n" is "nm".
This makes sense because in general, if "n" is an iterator,
then "n f" is "f" composed with itself "n" times. And, if "f"
is an iterator, then composing it with itself "n" is the same as
multiplying it with itself "n" times (since composition is used for
multiplication of iterators), and multiplying something by
itself "n" times is what is meant by raising it to the "n"th
exponent.
So, essentially, the "2" iterator acts as a squaring function,
when applied to other iterators. And, "3" acts as a cubing function.
And, "1" acts a function that raises a number to the power of "1"
(i.e., makes no change). And, "0" acts as a function that raises
a number to the power of "0" (i.e., always yields "1").
A note about our notation: although we often omit spaces in
expressions (as in "2Kx"), we will always leave a space between
the names of two iterators. That is, we will not write "32" if
we mean the cube of two; we will instead write "3 2". When we
do write "32", we are referring to the iterator for thirty-two.
There are several properties that numbers are traditionally
taken as having; here are some (where "^" is exponentiation):
These properties hold for all iterators "x", "y", and "z", as nearly
trivial consequences of the definitions we've given of
"+", "*", "^", "0", and "1". We won't bother to show how every
single one can be proven, but we will prove a few...
For instance, the property that
One particularly interesting property is
So, this property is the most fundamental property of "*" of all
(B's rewrite rule), and is a sort of definition of multiplication
in terms of exponentiation.
Similarly, the property
is a fundamental definition of addition in terms of
multiplication and exponentiation.
Now, it should not be thought that all properties of numbers
are trivial to prove with iterators. One that is typically
not-so-easy is
In a theory of iterators, this might be expressed as
Yet, this does not hold for all "x" and "y" (remember that composition
is not commutative). However, it does hold if "x" and "y" are both
iterators, but this is not a simple thing to prove (in fact, we
won't attempt to prove it here at all).
Up until now, we have only used iterators corresponding to
the natural numbers: 0, 1, 2, 3, (etc.). We thought of "2"
as the iterator applies a function twice; "1" is the iterator
that applies a function once; "0" is the iterator that applies
a function no times at all. If we continued the pattern, we
would take "-1" to be the iterator that "takes away" a function
from a parameter. In other words, "-1", given a function, would
yield the function's "inverse", a function that has the opposite
effect as the original.
Unfortunately, although iterators for "0", "1", "2", (etc.) could
be defined in terms of combinators, there is no way that this
can be done for "-1". For, consider our definitions of "3", "2", "1", and "0":
There does not seem to be a way to continue this pattern. However,
if we added an odd extension to our lambda construct, we could, in
this way:
But this is quite an abuse of the lambda construct, as we've currently
defined it.
An addition of a "-1" as a primitive would add great strength to
a language which otherwise could only express combinators, because,
using multiplication, it is possible to form all negative integers
(for instance, "B 3 (-1)" is "-3"). Also, fractions could be formed
by raising a integer to the power of "-1" (for instance, "(-1) 3"
is one third). Then, by raising numbers to fractional powers,
roots of numbers could be expressed (for instance, "(-1) 2 3" is the
square root of three, because "(-1) 2" is the inverse of the squaring
function, the square root function). Roots of negative numbers could be
used to express imaginary numbers.
However, because consideration of "-1" and similar functions would
cause many complications that we are not yet prepared to handle, we will
postpone discussing them further until a later chapter.
Often in this work we'll refer to compositions of various functions.
With our current syntax for composition, this can be quite cluttery.
For instance, the composition of functions "f", "g", "h", and "x"
might be written:
Since this is too cluttery, we introduce a new notation. In our
new notation, the above function would be written:
In general, "Bfg" will be abbreviated to "f * g". The use of "*" is,
of course, suggested by "B"'s use for multiplication.
Also, we will sometimes abbreviate "NBfg" to "f + g". This is
sometimes meaningful even when "f" and "g" are not iterators.
Whereas "*" is used for composing unary functions, "+" is
used to sort of "compose" binary functions. For instance,
"add + mul" is a function that multiplies by number and then
adds by the same number. That is, "(add + mul) 3" is a function
that multiplies by 3 and then adds 3, and is the same as
"add 3 * mul 3". Applying "(add + mul) 3" to, say, the number "2"
would give "add 3 (mul 3 2)", or in other words, "9".
This is the application of "K" upon "x" 3 times and then 2 more times.
In other words, it is "5Kx", or "K(K(K(K(Kx))))". We could have
seen this easily if we'd noticed that "NB 2 3" (the sum of 2 and 3)
is "5".
So, "3(2f)", given an "x", gives "f(f(f(f(f(fx)))))", just as
"6f" does.
The idea of using combinators in this way to represent natural numbers
originated with Alonzo Church in the early 1930s. Actually, Church
did not use the iterator for zero (he began with one); apparently,
he did not like the zero iterator, because it is a function ("KI")
that ignores its parameter (in general Church did not
like functions that ignore their parameters).
We've already mentioned several combinators, including I, B, C, W, K, S,
N, T, and several iterators, with these rewrite rules:
In this section, we'll describe several other interesting combinators,
primarily variations of the above combinators.
We've already used the B combinator extensively. Now we'll focus
on various iterations of "B". For instance, "2B" (read: "B squared"),
or in other words, "BBB" or "B * B", has the rewrite rule:
This is clear, because "(2B)fgxy" is the same as
Whereas "B" is used to compose a function "f" upon a unary
function "g", "2B" can be used to compose "f" upon a binary
function. For instance, "2B sqr plus" is a binary function
that adds two numbers and then squares the result.
Note that "B sqr plus" (as opposed to "2B sqr plus") is not particularly
meaningful; whereas "2B sqr plus" waits for two parameters "x" and "y"
(so to speak), giving them to "plus" before taking the square,
"B sqr plus" only waits for one parameter to give to "plus", and takes
the square (the square is then taken of an adding function then, rather
than a number). This actually could be meaningful after all
if "sqr" is interpreted as the "2" iterator; for sake of clarity,
however, we're using "sqr" and "plus" to mean the functions of
squaring and addition over numbers in the ordinary sense, not iterators.
Now, "3B", as one might expect, has the rewrite rule:
because "(3B)fgxyz" is the same as
"3B" could be useful when composing "f" with a tertiary function
"g" that needs to take 3 parameters before the result is passed
to "f". And, of course, "4B", "5B", (etc.) could be used for
compositions upon functions of 4, 5, and more parameters.
Unlike "B", when "C" is iterated, new interesting combinators
are not formed. For instance, "2C" is the same as "I", because "C(Cf)"
is in all cases the same as "f". This is because taking the converse
of a function one time flips the order of its two parameters, but
taking the converse again restores them to the original order.
Then, "3C" is the same as "C", and "4C" is the same as "I".
In general, if "n" is an iterator, then "nC" is either "C" or "I";
it is "C" if "n" is odd, but "I" if "n" is even.
The W combinator does yield interesting variations when iterated.
For instance, "2W" has the rewrite rule:
This is because "(2W)fx" is the same as
Whereas "W" was used to unify a binary function to a unary one,
"2W" can be used to unify a tertiary function to a unary one.
Then, as would be expected, "3W" can be used to unify 4-ary functions,
and has the rewrite rule:
This is clear because "(3W)fx" is the same as:
One can think of "3W" as making 3 duplicates of its second parameter,
"x" (making a total of 4 instances).
We've already mentioned some iterations of "K" in the last section.
We saw that while "K" can be used to form a function that ignores
a parameter, "2K" can be used to form a function that ignores two
parameters. In particular, "2K" has the rewrite rule:
We know this because "(2K)xyz" is the same as
Also, "3K" can be used to form a function that ignores three
parameters; it has the rewrite rule:
This is clear because "(3K)xyzf" is the same as
We'll now look at what is formed when "B", and iterations of "B",
are applied to "C". We've seen that "C" can be used to swap the
first two parameters of a function that is at least binary.
it has the rewrite rule:
Now, "BC" is similar to "C"; it takes a function and swaps
its second and third parameters (leaving the first intact).
It has the rewrite rule:
Note that the "y" and "z" are interchanged on the right.
To verify that "BC" behaves this way, see that "(BC)fxyz" is
the same as:
Now, "B(BC)", or in other words, "2BC", is also similar to "C".
It takes a function and swaps its third and fourth parameters
(leaving the first and second intact). It has the rewrite rule:
This can be verified by noting that "(2BC)fxyzg" is the same as:
As one might expect, "3BC" is like "2BC" except it postpones
the interchange for one more parameter (i.e., it swaps a function's
fourth and fifth parameters). In general, if "n" is an iterator,
then "nBC" takes a function and swaps its "n+1"th and
"n+2"th parameters.
We'll now look at the results of applying iterations of "B" to "W".
We know that "W" can be used on an at-least binary function to duplicate
its first parameter (i.e., make it take the place of the first and
second parameters); it had the rewrite rule:
This can be verified by noting that "(BW)fxy" is the same as:
As one might expect, "2BW", or in other words, "B(BW)", has the
rewrite rule:
This is clear because "(2BW)fxyz" is the same as:
It is clear that each time "B" is applied the operation of duplication
is postponed another parameter.
The situation with "K" is similar to that of "C" and "W".
We know that "K" can be used on a function (possibly a 0-ary function;
i.e., not a function at all) to yield a function like the original, but
with a "dummy" parameter inserted first in the parameter list. "K" has
the rewrite rule:
Now, "BK" is like "K", except that the second parameter of
the resulting function is ignored, instead of the first. "BK" has the
rewrite rule:
This is clear because "(BK)fxy" is the same as:
As one would expect, applying "2BK" to a function results in
the function but with a dummy parameter inserted after two real ones.
Then, "3BK" takes a function and inserts a dummy parameter after
three real ones.
Iterating "B" upon itself has some interesting results.
Recall that "B" essentially takes a function and yields a
function like the original, but with the first parameter "split"
into two (function and parameter). We see that "BB" is like
"B", except that it splits a function's second parameter
instead of its first:
Similarly, "2BB" would split a function's third parameter
(skipping over 2 of them):
This is clear because "(2BB)fxygz" is the same as:
We've now seen the results of iterating and composing the
basic combinators B, C, W, and K. In summary, iterating each
combinator three times gives:
Remember that by "*" we mean composition, and that iterating
a function yields that function's composition with itself
so many times.
Then, to summarize our discussion of compositions of B, C, W, and K,
note that composing each two times gives:
The B, C, W, and K combinators all take a function "f" and yield
a function like "f", but with the parameter list rearranged
(some parameters possibly duplicated, ignored, or applied
to each other). Because these combinators behave this way, they
are called "regular combinators". Applying "B" to any regular combinator
yields another regular combinator like the original but
with the effect on the parameter list postponed one parameter.
To more precisely define "regular combinator", we say that a
combinator is a regular combinator if and only if
it mentions its first parameter only one time, and at the very front of
the right side of the rewrite rule. The combinators I, B, C, W, K, and S
are all examples of regular combinators. The combinators T and M,
however, are irregular:
We'll now examine interesting variations of the C combinator
which we'll call "pushing" combinators; a pushing combinator is
a regular combinator that when applied to a function yields a function
like the original but with the function's first parameter pushed back
some number of parameters (i.e., the first parameter is postponed).
The C combinator is the most elementary pushing combinator; it postpones
a parameter back one place. The next pushing combinator is:
Essentially, applied to a function, it takes the function's converse,
pushing the first parameter back one place; then, "BC" is taken of the
result, swapping the function's new second parameter with the third,
pushing it back one further.
The next pushing combinator is:
This combinator takes a function, swaps its first parameter
with its second, its new second parameter with its third,
and then its new third parameter with its fourth; in the final
result, the original first parameter is swapped into the fourth place
and the other three are shifted forward.
The pushing combinators are quite useful; thus, we'll use
a special syntax for naming them ... "BC * C" will be called
simply "C2", and "2BC * BC * C" will be called "C3"
and so forth.
There is another kind of variation of "C", "pulling" combinators.
These behave in the opposite way as pushing combinators; whereas
a pushing combinator postpones a parameter some number of places,
a pulling combinator takes a parameter some number of places back
and pulls it to the front. That is, a pulling combinator, when
applied to a function of several parameters, yields a function like
the original but with one of the later parameters taken first.
The C combinator is the most elementary pulling combinator; it
pulls a function's second parameter to the front. The next
pulling combinator is:
When applied to a function, it swaps the function's second and
third parameters, then swaps the new second parameter with the first.
The result is that the third parameter is pulled to the first place
while the original first and second parameters are pushed back.
The next pulling combinator is:
This combinator pulls a function's fourth parameter to the front.
It is interesting that pulling combinators are formed in
quite a similar way to pushing combinators. Also, all pushing
combinators and pulling combinators can be formed from just "B"
and "C". For instance, the pulling combinator just mentioned would
be written without the "*" abbreviation as:
Because pulling combinators are quite useful, we also use
a special syntax for naming them;
will be called "C2-1", while
will be called "C3-1". This is a natural
way of naming pulling combinators, since they are inverses of
corresponding pushing combinators (the inverse of a function
"f" is commonly (and naturally) written "f-1").
So, applying "2W" to this unifies all three parameters, giving
This function could also have been written,
In general, if "m" and "n" are iterators, then "mK(nK)" is
a function that ignores "m" parameters, takes the important
parameter, ignores "n" more parameters, and yields the important
one. It takes a total of "m+n+1" parameters, "m+n" being the
number of parameters that are ignored.
Note that our last example, "2KI", could be written "2K(0K)";
as one would think from the rule stated above, it ignores two
parameters, takes the important one, doesn't ignore any more,
and yields the important one.
Then, applying "BC" to this would interchange the second and third
parameters, giving:
So, applying "BW" to this would duplicate the second parameter "y",
making it take the place of the third parameter "z" also, giving:
Answers to Problem Set 2
Answers to Problem Set 3
Answers to Problem Set 4
Answers to Problem Set 5
(f\g\x\ f(gx)) sqr succ
(g\x\ sqr (gx)) succ
x\ sqr (succ x)
Answers to Problem Set 6
Answers to Problem Set 7
Answers to Problem Set 8
B (times 3) (x\ minus x 3)
B (times 3) (C (x\ minus x) 3)
B (times 3) (C minus 3)
x\ B (minusfrom (sqr x)) (y\ sqr y)
x\ B (minusfrom (sqr x)) sqr (by eta-reduction)
C (x\ B (minusfrom (sqr x))) sqr
C (B B (x\ minusfrom (sqr x))) sqr
C (B B (B minusfrom (x\ sqr x))) sqr
C (B B (B minusfrom sqr)) sqr
f\g\x\ Bf(y\gxy)
f\g\x\ Bf(gx) (eta-reduction)
f\g\ B(Bf)(x\gx)
f\g\ B(Bf)g (eta-reduction)
f\ B(Bf)
BB(f\Bf)
BBB (eta-reduction)
Answers to Problem Set 9
f\ S (x\fx) (x\x)
f\ S f (x\x) (eta-reduction)
f\ S f I ("x\x" is I combinator)
C (f\ S f) I
CSI (eta-reduction)
Answers to Problem Set 10
f\g\h\x\ f(gx)(hx)
f\g\h\ S(Bfg)h
f\g\ S(Bfg)
f\ BS(Bf)
B(BS)B
Sfgx = fx(gx)
Nfghx = f(gx)(hx)
Historical Note
The function, f(x) = 2*x + 3
x. 2*x + 3
", the greek letter "lambda".
(We've avoided this notation because it is somewhat cluttery and
because it is difficult to get the lambda to match the font size in HTML).
One might also see
\x. 2*x + 3
\x-> 2*x + 3
Common Iterators: 2, 3, 4
2fx = f(fx)
3fx = f(f(fx))
4fx = f(f(f(fx)))
Problem Set 1 (Answers)
One and Zero
1fx = fx
0fx = x
Problem Set 2 (Answers)
Construction of Iterators from Other Combinators
0 = KI
2 = WB
f\x\ f(f(fx))
f\ Bf(Bff)
S(f\Bf)(f\Bff)
SB(WB)
f\x\ f(f(f(fx)))
f\Bf(Bf(Bff))
SB(f\Bf(Bff))
SB(SB(f\Bff))
SB(SB(WB))
The Successor Function
SB
n\f\ Bf(nf)
n\f\x\ f(nfx)
Problem Set 3 (Answers)
Addition
Nfghx = f(gx)(hx)
m\n\f\ B(mf)(nf)
m\n\f\x\ mf(nfx)
Problem Set 4 (Answers)
Multiplication
Problem Set 5 (Answers)
Exponentiation
Problem Set 6 (Answers)
Properties of Iterators
0 + x = x
1 * x = x
0 * x = 0
x ^ 1 = x
x ^ 0 = 1
(x + y) + z = x + (y + z)
(x * y) * z = x * (y * z)
(x + y) * z = (x * z) + (y * z)
z ^ (x + y) = (z ^ x) * (z ^ y)
z ^ (x * y) = (z ^ y) ^ x
(x * y) * z = x * (y * z)
can be proven by showing that "B" is associative, that "B(Bfg)h" is in all
cases the same as "Bf(Bgh)". This is fairly obvious, because
both "B(Bfg)h" and "Bf(Bgh)" give "f(g(hx))" when applied to a
parameter "x".
z ^ (x * y) = (z ^ y) ^ x
Written using "B" for "*", it says:
(Bxy)z = x(yz)
z ^ (x + y) = (z ^ x) * (z ^ y)
x * y = y * x
Bxy = Byx
Negative Numbers
3 = f\x\ f(f(fx))
2 = f\x\ f(fx)
1 = f\x\ fx
0 = f\x\ x
-1 = f\(fx)\ x
-2 = f\(f(fx))\ x
-3 = f\(f(f(fx)))\ x
New Notation for Composition
Bf(Bg(Bhx))
f * g * h * x
Answers to Problem Set 1
Answers to Problem Set 2
Answers to Problem Set 3
SBIfx
Bf(If)x (S's rewrite rule)
Bffx (I's rewrite rule)
f(fx) (B's rewrite rule)
as we'd expect the "2" iterator to.
SB(KI)fx
Bf(KIf)x (S's rewrite rule)
BfIx (K's rewrite rule)
f(Ix) (B's rewrite rule)
fx (I's rewrite rule)
Answers to Problem Set 4
B(2K)(3K)x (N's rewrite rule)
2K(3Kx) (B's rewrite rule)
Answers to Problem Set 5
3(2f)x
2f(2f(2fx))
2f(2f(f(fx)))
2f(f(f(f(fx))))
f(f(f(f(f(fx)))))
Answers to Problem Set 6
Historical Note
Ix = x
Bfgx = f(gx)
Cfxy = fyx
Wfx = fxx
Kxy = x
Sfgx = fx(gx)
Nfghx = f(gx)(hx)
Txf = fx
0fx = x
1fx = fx
2fx = f(fx)
3fx = f(f(fx))
Iterations of B
(2B)fgxy = f(gxy)
2Bfgxy
B(Bf)gxy (2's rewrite rule)
Bf(gx)y (B's rewrite rule)
f(gxy) (B's rewrite rule)
(3B)fgxyz = f(gxyz)
3Bfgxyz
B(B(Bf))gxyz (3's rewrite rule)
B(Bf)(gx)yz (B's rewrite rule)
Bf(gxy)z (B's rewrite rule)
f(gxyz) (B's rewrite rule)
Problem Set 1 (Answers)
Iterations of C
Problem Set 2 (Answers)
Iterations of W
(2W)fx = fxxx
2Wfx
W(Wf)x (2's rewrite rule)
Wfxx (W's rewrite rule)
fxxx (W's rewrite rule)
(3W)fx = fxxxx
(3W)fx
W(W(Wf))x (3's rewrite rule)
W(Wf)xx (W's rewrite rule)
Wfxxx (W's rewrite rule)
fxxxx (W's rewrite rule)
Problem Set 3 (Answers)
Iterations of K
(2K)xyz = x
2Kxyz
K(Kx)yz (2's rewrite rule)
Kxz (K's rewrite rule)
x (K's rewrite rule)
(3K)xyzf = x
3Kxyzf
K(K(Kx))yzf (3's rewrite rule)
K(Kx)zf (K's rewrite rule)
Kxf (K's rewrite rule)
x (K's rewrite rule)
Problem Set 4 (Answers)
Compositions of C
Cfxy = fyx
(BC)fxyz = fxzy
BCfxyz
C(fx)yz (B's rewrite rule)
fxzy (C's rewrite rule)
(2BC)fxyzg = fxygz
2BCfxyzg
B(BC)fxyzg
BC(fx)yzg
C(fxy)zg
fxygz
Problem Set 5 (Answers)
Compositions of W
Wfx = fxx
Similarly, "BW" can be used on an at-least tertiary function to
duplicate its second parameter, leaving the first parameter intact.
It has the rewrite rule:
(BW)fxy = fxyy
BWfxy
W(fx)y (B's rewrite rule)
fxyy (W's rewrite rule)
(2BW)fxyz = fxyzz
2BWfxyz
B(BW)fxyz (2's rewrite rule)
BW(fx)yz (B's rewrite rule)
W(fxy)z (B's rewrite rule)
fxyzz (W's rewrite rule)
Problem Set 6 (Answers)
Compositions of K
Kfx = f
(BK)fxy = fx
BKfxy
K(fx)y (B's rewrite rule)
fx (K's rewrite rule)
Problem Set 7 (Answers)
Compositions of B
(BB)fxgy = fx(gy)
(2BB)fxygz = fxy(gz)
2BBfxygz
B(BB)fxygz (2's rewrite rule)
BB(fx)ygz (B's rewrite rule)
B(fxy)gz (B's rewrite rule)
fxy(gz) (B's rewrite rule)
Problem Set 8 (Answers)
Summary
3B = B * B * B = f\g\x\y\z\ f(gxyz)
3C = C * C * C = f\x\y\ fyx
3W = W * W * W = f\x\ fxxxx
3K = K * K * K = f\x\y\z\ f
2BB = B(BB) = f\x\y\g\z\ fxy(gz)
2BC = B(BC) = f\x\y\z\g\ fxygz
2BW = B(BW) = f\x\y\z\ fxyzz
2BK = B(BK) = f\x\y\z\ fxy
Txf = fx
Mf = ff
Pushing Combinators
BC * C
2BC * BC * C
Problem Set 9 (Answers)
Pulling Combinators
C * BC
C * BC * 2BC
BC(B(BC)(B(BC)))
C * BC
C * BC * 2BC
Problem Set 10 (Answers)
Answers to Problem Set 1
x\y\z\ (x*y) + z
Answers to Problem Set 2
Answers to Problem Set 3
x\y\z\ (x*y) + z
x\ (x*x) + x
N plus sqr I
Answers to Problem Set 4
(2KI)xyz = z
(2K(2K))xyzfg = z
Answers to Problem Set 5
x\y\z\ (x*y) + z
x\y\z\ (x*z) + y
Answers to Problem Set 6
x\y\z\ (x*y) + z
x\y\ (x*y) + y
Answers to Problem Set 7
x\f\y\z\ (x*y) + z
Answers to Problem Set 8
f\x\y\z\ (fx * y) + z
x\f\y\z\ (x * fy) + z
x\y\f\z\ (x * y) + fz