Created
September 11, 2021 02:48
-
-
Save 0e4ef622/b321c7adb8f22346a38d41602628f413 to your computer and use it in GitHub Desktop.
A collection of functions for writing python programs using only lambdas.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# Fixed size binary numbers | |
true = lambda a: lambda b: a | |
false = lambda a: lambda b: b | |
and_ = lambda a: lambda b: a (b) (a) | |
or_ = lambda a: lambda b: a (a) (b) | |
xor = lambda a: lambda b: a (not_ (b)) (b) | |
not_ = lambda b: b (false) (true) | |
y = lambda f: (lambda x: x (x)) (lambda x: f (lambda v: x (x) (v))) | |
zero_gen = lambda z: lambda f: f (z) (z) | |
one_gen = lambda z: lambda o: lambda f: f (z) (o) | |
addc_gen = lambda add: lambda a: lambda b: lambda c: a ( | |
lambda al: lambda ar: b ( | |
lambda bl: lambda br: add (ar) (br) (c) ( | |
lambda rr: lambda c: add (al) (bl) (c) ( | |
lambda rl: lambda c: | |
lambda f: f (lambda g: g (rl) (rr)) (c))))) | |
add_gen = lambda add: lambda a: lambda b: add (a) (b) (false) (lambda n: lambda c: n) | |
mulw_gen_classic = (lambda mulw: lambda zero: lambda add: lambda neg: lambda x: lambda y: | |
x (lambda a: lambda b: y (lambda c: lambda d: | |
mulw (a) (c) (lambda e: lambda f: | |
mulw (a) (d) (lambda g: lambda h: | |
mulw (b) (c) (lambda i: lambda j: | |
mulw (b) (d) (lambda k: lambda l: | |
add (k) (h) (false) (lambda mr: lambda c1: | |
add (mr) (j) (false) (lambda mr: lambda c2: | |
add (g) (i) (c1) (lambda ml: lambda c3: | |
add (ml) (f) (c2) (lambda ml: lambda c4: | |
add (e) (zero) (c3) (lambda e: lambda _: | |
add (e) (zero) (c4) (lambda e: lambda _: | |
lambda f: f (lambda f: f (e) (ml)) (lambda f: f (mr) (l))))))))))))))) | |
mulw_gen_karatsuba = (lambda mulw: lambda zero: lambda addc: lambda neg: lambda x: lambda y: | |
x (lambda x1: lambda x0: y (lambda y1: lambda y0: | |
(lambda f: f (addc_gen (addc))) (lambda addc2: | |
(lambda f: f (add_gen (addc))) (lambda add: | |
(lambda f: f (add_gen (addc2))) (lambda add2: | |
(lambda f: f (mulw (x0) (y0))) (lambda z0: | |
(lambda f: f (mulw (x1) (y1))) (lambda z2: | |
addc (x0) (neg (x1)) (false) (lambda xd: lambda _: | |
addc (y1) (neg (y0)) (false) (lambda yd: lambda _: | |
(lambda f: f (mulw (xd) (yd))) (lambda p: | |
addc2 (p) (z2) (false) (lambda p: lambda c: | |
addc2 (p) (z0) (c) (lambda z1: lambda c: | |
z0 (lambda z01: lambda z00: | |
z1 (lambda z11: lambda z10: | |
z2 (lambda z21: lambda z20: | |
lambda f: (lambda f: f (z21) (add (z20) (z11))) (lambda f: f (add (z10) (z01)) (z00)))))))))))))))))) | |
mulw_gen = mulw_gen_karatsuba | |
mul_gen = (lambda mulw: lambda mul: lambda zero: lambda add: lambda x: lambda y: | |
x (lambda a: lambda b: y (lambda c: lambda d: | |
mulw (b) (d) (lambda k: lambda l: | |
add (k) (mul (a) (d)) (false) (lambda r: lambda _: | |
add (r) (mul (b) (c)) (false) (lambda r: lambda _: | |
lambda f: f (r) (l))))))) | |
not_gen = lambda nott: lambda n: n (lambda l: lambda r: lambda f: f (nott (l)) (nott(r))) | |
neg_gen = lambda _not: lambda one: lambda addc: lambda n: addc (one) (_not (n)) (false) (lambda n: lambda c: n) | |
# suffix meanings: | |
# z = zero | |
# o = one | |
# addc = add with carry | |
# add = add without carry | |
# mulw = multiply wide (return type is twice as wide) | |
# mul = regular multiply | |
# not = bitwise not | |
# neg = negate | |
bit_add = lambda a: lambda b: lambda c: (lambda ab: lambda f: f (xor (ab) (c)) (or_ (and_ (a) (b)) (and_ (ab) (c)))) (xor (a) (b)) | |
bit_mul = and_ | |
bit_mulw = lambda a: lambda b: lambda f: f (false) (and_ (a) (b)) | |
int2z = zero_gen (false) | |
int2o = one_gen (false) (true) | |
int2not = not_gen (not_) | |
int2addc = addc_gen (bit_add) | |
int2neg = neg_gen (int2not) (int2o) (int2addc) | |
int2mulw = mulw_gen (bit_mulw) (false) (bit_add) (lambda x: x) | |
int2mul = mul_gen (bit_mulw) (bit_mul) (false) (bit_add) | |
int4z = zero_gen (int2z) | |
int4o = one_gen (int2z) (int2o) | |
int4not = not_gen (int2not) | |
int4addc = addc_gen (int2addc) | |
int4neg = neg_gen (int4not) (int4o) (int4addc) | |
int4mulw = mulw_gen (int2mulw) (int2z) (int2addc) (int2neg) | |
int4mul = mul_gen (int2mulw) (int2mul) (int2z) (int2addc) | |
int8z = zero_gen (int4z) | |
int8o = one_gen (int4z) (int4o) | |
int8not = not_gen (int4not) | |
int8addc = addc_gen (int4addc) | |
int8neg = neg_gen (int8not) (int8o) (int8addc) | |
int8mulw = mulw_gen (int4mulw) (int4z) (int4addc) (int4neg) | |
int8mul = mul_gen (int4mulw) (int4mul) (int4z) (int4addc) | |
int16z = zero_gen (int8z) | |
int16o = one_gen (int8z) (int8o) | |
int16not = not_gen (int8not) | |
int16addc = addc_gen (int8addc) | |
int16neg = neg_gen (int16not) (int16o) (int16addc) | |
int16mulw = mulw_gen (int8mulw) (int8z) (int8addc) (int8neg) | |
int16mul = mul_gen (int8mulw) (int8mul) (int8z) (int8addc) | |
int32z = zero_gen (int16z) | |
int32o = one_gen (int16z) (int16o) | |
int32not = not_gen (int16not) | |
int32addc = addc_gen (int16addc) | |
int32neg = neg_gen (int32not) (int32o) (int32addc) | |
int32mulw = mulw_gen (int16mulw) (int16z) (int16addc) (int16neg) | |
int32mul = mul_gen (int16mulw) (int16mul) (int16z) (int16addc) | |
int64z = zero_gen (int32z) | |
int64o = one_gen (int32z) (int32o) | |
int64not = not_gen (int32not) | |
int64addc = addc_gen (int32addc) | |
int64add = add_gen (int64addc) | |
int64neg = neg_gen (int64not) (int64o) (int64addc) | |
int64mulw = mulw_gen (int32mulw) (int32z) (int32addc) (int32neg) | |
int64mul = mul_gen (int32mulw) (int32mul) (int32z) (int32addc) | |
def nm(n, width=64): | |
if width == 1: | |
return true if n else false | |
else: | |
width //= 2 | |
low_mask = (1 << width) - 1 | |
return lambda f: f (nm((n>>width) & low_mask, width)) (nm(n & low_mask, width)) | |
def unnm(n, width=64): | |
if width == 1: | |
return n(1)(0) | |
else: | |
width //= 2 | |
return n (lambda l: lambda r: (unnm(l, width) << width) | unnm(r, width)) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# Conversion to/from Church numerals | |
def nm(n): | |
if n == 0: return lambda f: lambda x: x | |
else: return lambda f: lambda x: f(nm(n-1)(f)(x)) | |
def unnm(n): return n(lambda x: x+1)(0) | |
true = lambda a: lambda b: a | |
false = lambda a: lambda b: b | |
and_ = lambda a: lambda b: a (b) (a) | |
or_ = lambda a: lambda b: a (a) (b) | |
not_ = lambda a: a (false) (true) | |
zero = false | |
succ = lambda n: lambda f: lambda x: f (n (f) (x)) | |
add = lambda n: lambda m: lambda f: lambda x: n (f) (m (f) (x)) | |
pred = lambda n: lambda f: lambda x: n (lambda g: lambda h: h (g (f))) (lambda u: x) (lambda u: u) | |
minus = lambda n: lambda m: m (pred) (n) | |
mul = (lambda n: lambda m: n | |
(lambda x: m | |
(lambda x: lambda f: lambda x: n (m (f)) (x)) | |
(zero)) | |
(zero)) | |
add = lambda n: lambda m: lambda f: lambda x: n (f) (m (f) (x)) | |
iszero = lambda n: n (lambda x: false) (true) | |
eq = lambda n: lambda m: and_ (iszero (minus (n) (m))) (iszero (minus (m) (n))) | |
less = lambda n: lambda m: not_ (leq (m) (n)) | |
leq = lambda n: lambda m: iszero (minus (n) (m)) | |
gtr = lambda n: lambda m: not_ (leq (n) (m)) | |
geq = lambda n: lambda m: leq (m) (n) | |
y = lambda f: (lambda x: x (x)) (lambda x: f (lambda v: x (x) (v))) | |
pair = lambda a: lambda b: lambda c: c (a) (b) | |
fst = lambda p: p (lambda a: lambda b: a) | |
snd = lambda p: p (lambda a: lambda b: b) | |
# Generic list | |
listinstance = lambda iemp: lambda cons: lambda hd: lambda tl: lambda nil: lambda c: c (iemp) (cons) (hd) (tl) (nil) | |
list = lambda i: lambda l: lambda c: c (i) (l) | |
listinstanceof = lambda l: l (lambda i: lambda l: i) | |
rawlist = lambda l: l (lambda i: lambda l: l) | |
nil = lambda i: i (lambda e: lambda c: lambda h: lambda t: lambda n: list (i) (n)) | |
isempty = lambda l: l (lambda i: lambda l: i (lambda e: lambda c: lambda h: lambda t: lambda x: e (l))) | |
cons = lambda h: lambda t: t (lambda i: lambda l: i (lambda e: lambda c: lambda x: lambda x: lambda x: list (i) (c (h) (l)))) | |
head = lambda l: l (lambda i: lambda l: i (lambda e: lambda c: lambda h: lambda t: lambda x: h (l))) # in case of empty list, undefined behavior | |
tail = lambda l: l (lambda i: lambda l: i (lambda e: lambda c: lambda h: lambda t: lambda x: list (i) (t (l)))) # in case of empty list, empty list | |
# List with Scott's encoding | |
scottnil = lambda n: lambda c: n | |
scottisempty = lambda l: l (true) (lambda x: lambda x: false) | |
scottcons = lambda h: lambda t: lambda n: lambda c: c (h) (t) | |
scotthead = lambda l: l (scottnil) (lambda h: lambda t: h) | |
scotttail = lambda l: l (scottnil) (lambda h: lambda t: t) | |
newlist = list (listinstance (scottisempty) (scottcons) (scotthead) (scotttail) (scottnil)) (scottnil) | |
lmap = lambda F: lambda l: y (lambda f: lambda l: isempty (l) (lambda x: l) (lambda x: cons (F (head (l))) (f (tail (l)))) (l)) (l) | |
length = (lambda l: y (lambda f: lambda l: | |
(isempty(l) | |
(lambda x: zero) | |
(lambda x: succ (f (tail (l)))) | |
(l))) | |
(l)) | |
take = (lambda n: lambda l: y (lambda f: lambda n: lambda l: | |
(or_ (isempty(l)) (iszero (n)) | |
(lambda x: nil (listinstanceof (l))) | |
(lambda x: cons (head (l)) (f (pred (n)) (tail (l)))) | |
(n))) | |
(n) (l)) | |
skip = lambda n: lambda l: n(tail)(l) | |
takewhile = (lambda p: lambda l: y (lambda f: lambda l: | |
(isempty(l) (lambda x: true) (lambda x: p (head (l))) (l) | |
(lambda x: cons (head (l)) (f (tail (l)))) | |
(lambda x: nil (listinstanceof (l))) | |
(l))) | |
(l)) | |
skipwhile = (lambda p: lambda l: y (lambda f: lambda l: | |
(isempty(l) (lambda x: false) (lambda x: p (head (l))) (l) | |
(lambda x: f (tail (l))) | |
(lambda x: l) | |
(l))) | |
(l)) | |
foldr = (lambda F: lambda a: lambda l: y (lambda f: lambda a: lambda l: | |
(isempty(l) | |
(lambda x: a) | |
(lambda x: F (head (l)) (f (a) (tail (l)))) | |
(l))) | |
(a) (l)) | |
foldl = (lambda F: lambda a: lambda l: y (lambda f: lambda a: lambda l: | |
(isempty(l) | |
(lambda x: a) | |
(lambda x: f (F (a) (head (l))) (tail (l))) | |
(l))) | |
(a) (l)) | |
filter = lambda p: lambda l: foldr (lambda e: lambda a: p (e) (cons (e) (a)) (a)) (nil (listinstanceof (l))) (l) | |
reverse = lambda l: foldl (lambda a: lambda e: cons (e) (a)) (nil (listinstanceof (l))) (l) | |
trim = lambda p: lambda l: (reverse (skipwhile (p) (reverse (skipwhile (p) (l))))) | |
concat = (lambda a: lambda b: y (lambda f: lambda a: | |
(isempty (a) | |
(lambda x: b) | |
(lambda x: cons (head (a)) (f (tail (a)))) | |
(a))) | |
(a)) | |
padr = lambda n: lambda c: lambda s: y (lambda f: lambda s: lambda n: | |
(iszero (n) | |
(lambda x: s) | |
(isempty (s) | |
(lambda x: cons (c) (f (s) (pred (n)))) | |
(lambda x: cons (head (s)) (f (tail (s)) (pred (n))))) | |
(n))) (s) (n) | |
# Conversion for lists containing numbers | |
def lsn(l): | |
if len(l) == 0: return newlist | |
else: return cons(nm(l[0]))(lsn(l[1:])) | |
def unlsn(l): | |
if isempty(l)(True)(False): return [] | |
else: return [unnm(head(l))] + unlsn(tail(l)) | |
dividesBy = (lambda d: lambda n: | |
y (lambda f: lambda n: | |
iszero (n) | |
(lambda x: false) | |
(and_ (iszero (minus (n) (d))) (iszero (minus (d) (n))) | |
(lambda x: true) | |
(lambda x: f (minus (n) (d)))) | |
(n)) | |
(n)) | |
divide = (lambda n: lambda m: y | |
(lambda f: lambda n: | |
(lambda d: d | |
(lambda x: lambda x: succ (f (d))) | |
(lambda x: zero) | |
(n) | |
) (minus (n) (m))) | |
(succ (n))) | |
# divrem = (lambda n: lambda m: y | |
# (lambda f: lambda n: | |
# (lambda r: r | |
# (lambda x: lambda x: (lambda r: pair (succ (fst (r))) (snd (r))) (f (pred (r)))) | |
# (lambda x: pair (zero) (n)) | |
# (n) | |
# ) (minus (succ (n)) (m))) | |
# (n)) | |
split = lambda p: lambda l: y (lambda f: lambda t: | |
(isempty (t) (lambda x: newlist) | |
(lambda x: (lambda r: cons (fst (r)) (f (snd (r)))) (splitpre (p) (t))) | |
(t))) (l) | |
splitpre = lambda p: lambda l: y (lambda f: lambda l: | |
(isempty (l) (lambda x: true) (lambda x: (p (head (l)))) (l) | |
(lambda x: pair (nil (listinstanceof (l))) (tail (l))) | |
(lambda x: (lambda r: pair (cons (head (l)) (fst (r))) (snd (r))) (f (tail (l))))) | |
(l)) (l) | |
# realm of not as pure | |
seq = lambda a: lambda b: b(a(a)) | |
prntn = lambda n: lambda f: f (print(unnm(n), end='')) | |
prntsln = lambda s: lambda f: f (print(s)) | |
prnts = lambda s: lambda f: f (print(s, end='')) | |
inp = lambda s: lambda f: f (input(s)) | |
ret = lambda a: lambda f: f (a) | |
# Python strings as a list | |
pysnil = "" | |
def pysisempty(l): | |
if len(l) == 0: return true | |
else: return false | |
pyscons = lambda h: lambda t: h+t | |
pyshead = lambda l: l[0] | |
pystail = lambda l: l[1:] | |
pysnew = lambda s: list (listinstance (pysisempty) (pyscons) (pyshead) (pystail) (pysnil)) (s) | |
# Python lists as a list | |
pylnil = [] | |
pylisempty = lambda l: len(l) == 0 and true or false | |
pylcons = lambda h: lambda t: [h] + t | |
pylhead = pyshead | |
pyltail = pystail | |
pylnew = list (listinstance (pylisempty) (pylcons) (pylhead) (pyltail) (pylnil)) ([]) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment