# Simpler two-combinator base

## Brent Kerby — 2002-04-07 08:17:07

    Yup. There's a simpler one. Call it {y, k}, where

    [C] [B] [A] y == A [[C] [C] B]

        [B] [A] k == A

    I don't really have much to say about this, except here's the basic

    constructions:

    i    == [k] [[]] y k

    cons == [[] k k] [] y [] y

    dip  == [k] [[k]] y y

    dup  == [] [[]] y k

    zap  == [] k

    Here's a proof of those constructions ...

    (i:)

       [A] [k] [[]] y k

    == [] [[A] [A] k] k

    == [A] [A] k

    == A

    (cons:)

       [B] [A] [[] k k] [] y [] y

    == [B] [[A] [A] [] k k] [] y

    == [[B] [B] [A] [A] [] k k]

    == [[B] [B] [A] k]

    == [[B] A]

    (dip:)

       [B] [A] [k] [[k]] y y

    == [B] [k] [[A] [A] k] y

    == [A] [A] k [[B] [B] k]

    == A [[B] [B] k]

    == A [B]

    (dup:)

       [A] [] [[]] y k

    == [] [[A] [A]] k

    == [A] [A]

    (zap: okay I think we know this one)

    And just for fun (yes, there is a four-way tie for the shortest construction

    of sip):

    sip == [[k]] [y k] [[k]] y y y

        == [k] [[k]] [y k] [] y y y

        == [k] [[[k]] [[]] y k] y y

        == [k] [[] [[]] y k [k]] y y

    Now, the final challenge is to find a two-combinator base in which both

    combinators take only two parameters.

    - Brent