Skip to content

Instantly share code, notes, and snippets.

@dbramucci
Last active February 3, 2020 23:42
Show Gist options
  • Save dbramucci/66dd1f99190611d64b1aeb69894253d9 to your computer and use it in GitHub Desktop.
Save dbramucci/66dd1f99190611d64b1aeb69894253d9 to your computer and use it in GitHub Desktop.
Fibonacci implemented with barely any use of anything that isn't a function
def Zero(zero_val):
return lambda rec_func: zero_val
def Succ(nat):
return lambda zero_val: lambda rec_func: rec_func(nat)
def add(a):
return (lambda b:
a
(b)
(lambda prev_a:
Succ(add(prev_a)(b))
)
)
def sub(a):
return (lambda b:
b
(a)
(lambda prev_b:
a
(Zero) # This means 2 - 3 = 0, saturating subtraction
(lambda prev_a:
sub(prev_a)(prev_b)
)
)
)
def mult(a):
return (lambda b:
a
(Zero)
(lambda prev_a:
prev_a
(b)
(lambda _:
add
(b)
(mult(b)(prev_a))
)
)
)
def funcFalse(a):
return lambda b: a
def funcTrue(a):
return lambda b: b
def And(a):
return lambda b: a(funcFalse)(b(funcFalse)(funcTrue))
def Or(a):
return lambda b: a(b(funcFalse)(funcTrue))(funcTrue)
def Not(a):
return a(funcTrue)(funcFalse)
def Eq(a):
return (lambda b:
a
(b(funcTrue)(lambda _: funcFalse)) # If a is zero and b is zero, true, if b isn't zero,
(lambda prev_a:
b
(funcFalse)
(lambda prev_b:
Eq(prev_b)(prev_a)
)
)
)
def Leq(a):
return (lambda b:
a
(funcTrue)
(lambda prev_a:
b(funcFalse)(lambda prev_b: Leq(prev_a)(prev_b))
)
)
def Geq(a):
return lambda b: Leq(b)(a)
def Le(a):
return lambda b: And(Leq(a)(b))(Not(Eq(a)(b)))
def Gr(a):
return lambda b: Le(b)(a)
def flip(f):
return lambda a: lambda b: f(b)(a)
def pair(a):
return lambda b: lambda p: p(a)(b)
def left(a):
return lambda b: a
def right(a):
return lambda b: b
def let(x):
return lambda f: f(x)
def let_pair(p):
return lambda f: f(p(left))(p(right))
def quotRem(n):
return (lambda d:
n
(pair(Zero)(Zero))
(lambda prev_n:
let_pair
(quotRem(prev_n)(d))
(lambda q:
(lambda r:
(Eq(Succ(r))(d)
(pair(q)(Succ(r)))
(pair(Succ(q))(Zero))
)
)
)
)
)
One = Succ(Zero)
Two = Succ(One)
Three = Succ(Two)
Four = mult(Two)(Two)
Five = Succ(Four)
Six = Succ(Five)
Seven = Succ(Six)
Eight = mult(Two)(Four)
Nine = Succ(Eight)
Ten = Succ(Nine)
Eleven = Succ(Ten)
Twelve = Succ(Eleven)
Thirteen = Succ(Twelve)
Fourteen = Succ(Thirteen)
Fifteen = Succ(Fourteen)
Sixteen = mult(Two)(Eight)
Seventeen = Succ(Sixteen)
Eighteen = Succ(Seventeen)
Nineteen = Succ(Eighteen)
Twenty = Succ(Nineteen)
def nat_to_digit(nat):
return (nat('0')
(lambda One:
One('1')
(lambda Two:
Two('2')
(lambda Three:
Three('3')
(lambda Four:
Four('4')
(lambda Five:
Five('5')
(lambda Six:
Six('6')
(lambda Seven:
Seven('7')
(lambda Eight:
Eight('8')
(lambda Nine:
Nine('9')
(lambda _: 'error, not digit')
)
)
)
)
)
)
)
)
)
)
def nat_to_string(nat):
return (Leq(nat)(Nine)
(lambda:
let_pair
(quotRem(nat)(Ten))
(lambda q:
(lambda r:
nat_to_string(q) + nat_to_digit(r)
)
)
)
(lambda: nat_to_digit(nat))
)() # Lambda needed to avoid computing branch not used
def nat_to_int(nat):
return nat(0)(lambda x: nat_to_int(x) + 1)
def int_to_nat(n):
nat = Zero
for _ in range(n):
nat = Succ(nat)
return nat
def nat_fib(nat):
return (
nat
(One)
(lambda nat_prev:
nat_prev
(One)
(lambda nat_prev_prev:
add
(nat_fib(nat_prev))
(nat_fib(nat_prev_prev))
)
)
)
def fibonacci(n):
return nat_to_string(nat_fib(int_to_nat(n)))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment