A combinator is a function that inputs a combinator and outputs another combinator. The combinator xy is the output of x with input y. There are many combinators. Each combinator has a formula for its output in terms of its input. For example, the identity combinator I always outputs the input. The formula for the identity combinator is Ix=x.

Two useful combinators are S and K. They have the following formulas.
((Sx)y)z=(xz)(yz)
(Kx)y=x

1. Derive I from S and K.
2. Derive B from S and K such that ((Bx)y)z=x(yz) for all x, y, and z.
3. Derive C from S and K such that ((Cx)y)z=(xz)y for all x, y, and z.
4. Prove that all combinators can be derived from S and K.

There are no comments yet.