Church BooleansX B SsmOo234 LmCc 1 Rل YDd 2yz Uu MmH 0WKre Z7d Z
Church booleans
A Church boolean is a function that returns x for true and y for false where x is the first argument to the function and y is the second argument to the function. Further functions can be composed from these functions which represent the and not or xor and implies logical operations.
Challange
Construct the Church booleans and and not or xor and implies Church gates in a language of your choice. And or and xor should take in two functions (representing Church booleans) and return a function (representing another Church boolean). Likewise, not should invert a the function it takes and the implies gate should perform boolean implies logic where the first argument implies the second.
Scoring
The total length of all of the code required to make Church true and false in your language and the and not or xor and implies Church gates excluding the function's name. (for example, false=lambda x,y:y in Python would be 13 bytes). You can reuse these names later in your code with them counting 1 byte toward the byte total of that gate.
Pseudo code Examples:
The functions you create should be able to be called later in your code like so.
true(x, y) -> x
false(x, y) -> y
and(true, true)(x, y) -> x
and(true, false)(x, y) -> y
# ... etc
6 Answers
Haskell, 50 - 6 = 44 bytes
-1 byte thanks to Khuldraeseth na'Barya, and -1 byte thanks to Christian Sievers.
t=const
f=n t
n=flip
a=n n f
o=($t)
x=(n>>=)
i=o.n
Try it online!
-
\\$\\begingroup\\$ Side note: you can define
Showinstances forconstandconst idand print the church booleans directly. Try it online!. \\$\\endgroup\\$ – nimi 10 hours ago -
\\$\\begingroup\\$
acan be shortened. \\$\\endgroup\\$ – Khuldraeseth na'Barya 9 hours ago -
3\\$\\begingroup\\$ Why is no one using
f=n t? \\$\\endgroup\\$ – Christian Sievers 7 hours ago -
2\\$\\begingroup\\$ You can save a byte by using
t=pureinstead oft=const. \\$\\endgroup\\$ – Joseph Sible 5 hours ago -
\\$\\begingroup\\$ @JosephSible I tried that initially. Unfortunately,
t=purewill cause an error when I try to applya,o,x, orito it. Declaring the type oftto fix this costs more bytes than just usingt=const. \\$\\endgroup\\$ – Nitrodon 3 hours ago
Python 2, 133 - 6 = 127 94 bytes
exec"t!u;f!v;n!u(f,t);a!u(v,f);o!u(t,v);x!u(n(v),v);i!o(v,n(u))".replace('!','=lambda u,v=0:')
Try it online!
Shamelessly stealing the sneaky idea behind Jonathan Allan's answer; no bytes deducted though.
-
\\$\\begingroup\\$ I was going to post an answer to my own question but I was unsure if this was allowed and I think that this is against the spirit of it. So I think I will just guide you along instead. Instead of using lists, is there anyway you can use the functions that are being input themselves and the specific manner in which they return their inputs to shorten the code? \\$\\endgroup\\$ – Ryan Schaefer 12 hours ago
-
\\$\\begingroup\\$ I'd wager that although the answer is yes, it would be considerably longer in Python. \\$\\endgroup\\$ – Unrelated String 12 hours ago
-
\\$\\begingroup\\$ I stand corrected \\$\\endgroup\\$ – Unrelated String 12 hours ago
-
\\$\\begingroup\\$ @Mr.Xcoder you are correct, I had the wrong number of bytes for the example function. They would be allowed to remove 6 bytes though for the names of the functions. \\$\\endgroup\\$ – Ryan Schaefer 10 hours ago
-
\\$\\begingroup\\$ @Mr. Xcoder: Modified as per your observations. \\$\\endgroup\\$ – Chas Brown 6 hours ago
JavaScript (Node.js), 92 - 7 = 85 bytes
t=p=>q=>p
f=p=>q=>q
n=p=>q=>r=>p(r)(q)
a=p=>q=>p(q)(f)
o=p=>p(t)
x=p=>p(n)(f())
i=p=>o(n(p))
Try it online! Link includes basic test cases.
-
\\$\\begingroup\\$ @Mr.Xcoder That's not how I understood the scoring system, although it's changed again since so I restored 7 bytes anyway. \\$\\endgroup\\$ – Neil 10 hours ago
-
1\\$\\begingroup\\$ Will
n=p=>p(f)(t)work? \\$\\endgroup\\$ – tsh 3 hours ago -
1\\$\\begingroup\\$ Will
a=p=>n(p)(f)work? \\$\\endgroup\\$ – tsh 3 hours ago
Python 2, 101 - 3 = 98 bytes
David Beazley eat your heart out!
exec'=lambda x,y=0'.join('F :y;T :x;N :x(F,T);A :x(y,F);O :x(T,y);X :x(N(y),y);I :O(y,N(x))'.split())
Try it online!
I think 101 - 3 because I don't reuse the functions A, X, or I, but I use a single = for assignment (in front of lambda). Maybe I cant remove any?
-
\\$\\begingroup\\$ @Ryan Schaefer can I remove three or does my use of
execmean I cannot? I can see going either way - I don't reuse A, X, or I but the code wont work without them. (Maybe I even get to remove 3.5?!) \\$\\endgroup\\$ – Jonathan Allan 9 hours ago -
\\$\\begingroup\\$ 95 bytes (before the -3) \\$\\endgroup\\$ – Chas Brown 4 hours ago
J, 67 bytes - 7 = 60
t=.[
f=.]
n=.~
a=.2 :'u v]'
o=.2 :'[u v'
x=.2 :'u~v u'
i=.2 :'v u['
Try it online!
Worth noting:
Higher order functions work differently in J than in a functional language. To create a new verb from 1 or 2 existing verbs, you need to use either an adverb (in the case of 1) or a conjunction (in the case of 2).
Syntactically, adverbs come after a verb, and conjunctions go between them. Thus to "not" a verb f you do f n, and to "and" verbs f and g, you f a g.
C++17, 207 − 49 = 158 bytes
The linebreaks are unnecessary (other than the first one).
#define A auto
#define D(v,p)A v=[](A x,A y){return p;};
D(true_,x)
D(false_,y)
A not_=[](A f){return[f](A x,A y){return f(y,x);};};
D(and_,x(y,false_))
D(or_,x(true_,y))
D(xor_,x(not_(y),y))
D(implies,x(y,true_))
Try it online!
Unit-tested with assertions such as:
static_assert('L' == true_('L', 'R'));
static_assert('R' == not_(true_)('L', 'R'));
static_assert('L' == and_(true_, true_)('L', 'R'));
static_assert('L' == or_(true_, true_)('L', 'R'));
static_assert('R' == xor_(true_, true_)('L', 'R'));
static_assert('L' == implies(true_, true_)('L', 'R'));
true([x, y]),and([true, true])([x, y]))? \\$\\endgroup\\$ – ar4093 1 hour ago