A collection of functions for writing python programs using only lambdas.

binary.py

# 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))

lamb.py

# 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)) ([])