comp = lambda f: lambda g: lambda x: f(g(x))

zero = lambda f: lambda x: x
one = lambda f: lambda x: f(x)
two = lambda f: lambda x: f(f(x))
three = lambda f: lambda x: f(f(f(x)))
four = lambda f: lambda x: f(f(f(f(x))))

succ = lambda n: lambda f: lambda x: f (n (f) (x))
plus = lambda m: lambda n: lambda f: comp (m(f)) (n(f))
mult = lambda m: lambda n: lambda f: m (n (f))

# convert Church-encoded number to native Python int
to_python_int = lambda n: n (lambda x: x+1) (0)

if_zero_then_else = lambda n:lambda x:lambda y: n (lambda z:y) (x)

pair = lambda x: lambda y: lambda z: z(x)(y)
fst = lambda p: p (lambda x: lambda y: x)
snd = lambda p: p (lambda x: lambda y: y)

none = lambda n: lambda s: n
some = lambda x: lambda n: lambda s: s (x)
switch = lambda o: lambda n: lambda s: o (n) (s)

# list constructor : cons (head) (tail)
# (empty list = none)
cons = lambda h: lambda t: lambda _: lambda f: f (h) (t)

my_list = cons (three) (
    cons (four) (
        cons (plus (three) (two)) (
            cons (mult (two) (three)) (
                none
))))

my_longer_list = cons (one) (cons (two) (my_list))

leng = lambda s: lambda l: switch (l) (zero) (lambda h: lambda t: succ (s(t)))

Y = lambda f: (lambda x: f (x (x))) (lambda x: f (x (x)))

Z = lambda f: \
    (lambda x: f (lambda y: x (x) (y))) (lambda x: f (lambda y: x (x) (y)))

length = Z (leng)

to_python_int(length(my_list))
to_python_int(length(my_longer_list))


#### more advanced examples

pred = lambda n: lambda f: lambda x: \
       snd (n (lambda p: pair (f(fst(p))) (fst(p))) (pair (x) (x)))

if_smaller_then_else = lambda m: lambda n: lambda x: lambda y: \
                       if_zero_then_else (n (pred) (m)) (x) (y)

tree = lambda v: lambda l: lambda r: lambda _: lambda f: f (v)(l)(r)

ins = lambda i: lambda t: lambda v: switch (t) (tree (v) (none) (none)) \
      (lambda w: lambda l: lambda r: if_smaller_then_else (v) (w) \
       (tree (w) (i (l) (v)) (r)) (tree (w) (l) (i (r) (v))))


insert = Z (ins)

left_subtree = lambda v: lambda l: lambda r: l
right_subtree = lambda v: lambda l: lambda r: r
node_label = lambda v: lambda l: lambda r: v



tpl = lambda rec: lambda t: switch (t) ([]) \
      (lambda w: lambda l: lambda r: rec (l) + [to_python_int (w)] + rec (r))

to_python_list = Z (tpl)

my_pretty_tree = insert (none) (three)
my_pretty_tree = insert (my_pretty_tree) (two (two))
my_pretty_tree = insert (my_pretty_tree) (mult (four) (zero))
my_pretty_tree = insert (my_pretty_tree) (plus (three) (two))
my_pretty_tree = insert (my_pretty_tree) (succ (succ (four)))
my_pretty_tree = insert (my_pretty_tree) (pred (pred (mult (three) (four))))
my_pretty_tree = insert (my_pretty_tree) (mult (three) (three))

to_python_list (my_pretty_tree)