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