More or less well-known examples of one-point bases, including Iota, as well as similar and even smaller alternatives. On the right, S, K and I combinators are defined in terms of the respective basis X.

One-point bases for λ-calculus

The Iota combinator and some alternatives

I first read about the Iota combinator years ago and was intrigued by its existence. Recently I wondered what some alternative one-point bases look like and whether Iota is the smallest such combinator. Here is what I found online, in papers, and from writing a small tool that searches for such bases.

Indeed, the tool found some that are smaller than Iota. I’m sure they have been found before, but it seems this information could be more discoverable. So here is a buffet of one-point bases; after a quick, informal recap/definition of what a (one-point) basis is.

Disclaimer: This is not a tutorial or introduction to λ-calculus or combinatory logic. Yet, maybe this still sparks the curiosity of less experienced readers, so further reading is linked throughout!

Basis

A basis for λ-calculus or combinatory logic is a set of terms that, when combined using nothing but function application, can generate (terms equal to) any arbitrary λ-term or combinator.

Example: Basis {S, K, I} where

I = λx -> x
K = λx -> λy -> x
S = λx -> λy -> λz -> x z (y z)
or equivalently
I x = x
K x y = x
S x y z = x z (y z)

For instance, the λ-term λf -> λx -> f (f x) (a Church encoded number 2) is equivalent to S (S (K S) K) I, which one can confirm with pen and paper.

Alternatively, the combinator C with behavior C x y z = x z y can be reconstructed as S (S (K (S (K S) K)) S) (K K).

It is worth noting that even {S, K} is a basis: One can reconstruct I = S K K. The second K can in fact be any arbitrary term for this to work.

Counter-example: Set {K, I} with K and I defined as above. The two terms lack the ability to duplicate terms (like combinator S does via argument z). Thus, λ-term λx -> x x (also known as the M combinator) cannot be reconstructed using any combination of Ks and Is.

One-point bases

A one-point basis is a basis with just one element. There exist infinitely many. In the following we consider a basis {X}, but for various definitions of X.

The Iota combinator

Consider the Iota combinator X = λx -> x "S" "K" with S and K as defined above. Note that if {X} is our basis, S and K should be defined in terms of X, instead of the other way around! “S” and “K” above are hence meant as compact notation for the full definition:

X = λx -> x (λx -> λy -> λz -> x z (y z)) (λx -> λy -> x)
            -------------S--------------- -------K-------

{X} is a basis since {S, K, I} is and we can reconstruct I = X X, K = X (X I) and S = X K.

Similar alternatives

While Iota is rather well-known and quite elegant, there are several similar combinators that form one-point bases like

• X = λx -> x "K" "S", since S = X X X and K = X (S X X)
• X = λx -> x "K" "S" "K", since K = X X X and S = X (X X)

More compact alternatives

The above one-point bases are quite lengthy λ-terms (when fully expanded), so I wrote a tool to search for shorter alternatives and found:

X = λx -> λy -> λz -> x (λx -> λy -> x) z (y z)
    -------------S-ish--               --------
                         ------K------

As indicated, note how this is similar to the S combinator, but with an additional K in the body. Not sure if/where this was mentioned in literature before, but I am inclined to call this combinator “Ioter” since “Iota” already means “small amount”, and this combinator is smaller.

Anyways, while Ioter is small, it unfortunately requires rather lengthy terms to reconstruct well-known combinators:

I = X (X (X (X (X X X)))) X
K = X (X (X (X X X))) X
S = X (K (K X)) K 

The construction for S is likely not the shortest (after expanding the Ks, it uses 23 Xs), but I believe no definition using less than 15 Xs exists.

EDIT: Indeed, John Tromp found S = (X(X(X X(X(X(X X)))))) (X(X(X X) X) X) X of size 16. Thank you!

A very similar, slightly longer (but still shorter than Iota) alternative is:

X = λx -> λy -> λz -> x (λx -> λy -> λz -> y) z (y z)
    -------------S-ish--                     --------
                         --------K K--------

One can restore S, K and I from this basis slightly faster:

I = X X
K = X I I
S = X (K (K X)) K

Conclusion

As mentioned at the beginning, the point of this post is mainly to have a quick overview with examples in one spot. I show the Iota combinator as well as similar and smaller alternatives that I was previously unaware of. They have drawbacks in restoring SKI combinators, but I’m still intrigued; anyways, this is not supposed to be a ranking and purely for reference (see title image) or entertainment.