# Common combinators
I = x: x;
K = x, y: x;
S = x, y, z: x z (y z);
Y = (a: a a) (a, f: f (a a f));

# Booleans
T = K;
F = K I;
Not = p, a, b: p b a;
And = p, q: p q F;
Or = p, q: p T q;
Xor = p, q: p Not I q;

# Pairs/lists
[] = K T;
[]? = l: l (h, t: F);
Cons = h, t, x: x h t;
Head = l: l T;
Tail = l: l F;

# Church arithmetic
+1 = n, f, x: f (n f x);
+ = m, n, f, x: m f (n f x);
* = m, n, f: m (n f);
^ = m, n: n m;
-1 = n, f, x: n (g, h: h (g f)) (K x) I;
- = m, n: n -1 m;
0? = n: n (K F) T;

# Church numerals
0 = f, x: x;
1 = f, x: f x;
2 = +1 1;
3 = +1 2;
4 = ^ 2 2;
5 = + 2 3;
6 = * 2 3;
7 = +1 6;
8 = ^ 2 3;
9 = ^ 3 2;
10 = * 2 5;
16 = ^ 2 4;
20 = * 2 10;
30 = * 3 10;
32 = ^ 2 5;
64 = ^ 2 6;
100 = ^ 10 2;
128 = ^ 2 7;
256 = ^ 2 8;
512 = ^ 2 9;
1k = ^ 10 3;
1ki = ^ 2 10;
1m = ^ 10 6;
1mi = ^ 2 20;
1g = ^ 10 9;
1gi = ^ 2 30;

# Recursive functions
FactY = Y (f, n: (0? n) 1 (* (f (-1 n)) n));
Fact = n: n (f, i: * (f (+1 i)) i) (K 1) 1;
Fibo = n: n (f, a, b: f (+ a b) a) F 1 0;