Another base !

Brent Kerby — 2002-04-07 09:18:48

Okay, you all are probably getting tired of this. But here's another

complete two-combinator base. We'll call it {g, k}:



[B] [A] g == [[B] A] [A [B]]

[B] [A] k == A



The "g" here is sort of a combination of "cons" and "take", contrived to

allow "cons" and "dip" to be easily sucked back out of it. It's actually a

rather beautiful combinator, though, considering its symmetry. Also, the

basic constructions turn out beautifully:



dip  == g k

cons == g [] k

i    == [[]] g k k    ==  [[]] dip k

dup  == [] g g k g k  ==  [] g dip dip



Here's the proof of those constructions:



(dip:)

   [B] [A] g k

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

== A [B]



(cons:)

   [B] [A] g [] k

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

== [[B] A]



(i:)

   [A] [[]] dip k

== [] [A] k

== A



(dup:)

   [A] [] g dip dip

== [[A]] [[A]] dip dip

== [A] [[A]] dip

== [A] [A]



And, interestingly, here's the shortest construction of sip:



sip == [[] g g k g k] g k g k

    == [dup] dip dip



This is kinda cool because "[dup] dip dip" is the standard construction of

"sip".



Well, I'm pretty happy that this neat of a base exists. We could perhaps

look for a bit simpler one by demanding a "g" that only duplicates one of

its parameters (instead of both); however, based on some observations after

looking quite a bit for such a base, I don't think it exists (providing we

still demand that both combinators take only two parameters), although I

could be wrong.



- Brent

Manfred von Thun — 2002-04-08 04:39:20

On Sun, 7 Apr 2002, Brent Kerby wrote:



 > Okay, you all are probably getting tired of this.



 
No, on the contrary. You do not cease to amaze me.

I hope other pressures do not cause you to run out of steam

before you have a chance to write it all up.



The {g, k} base is indeed bautiful.

When you have settled on the base of primitives that you need

I'll be vary happy to put theminto the standard distribution.



  - Manfred