Forgive me if you've heard this one before.
Python, 56 lines
Download
Copy to clipboard1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 | # Iota
#
# http://semarch.linguistics.fas.nyu.edu/barker/Iota/
#
# S = λx.λy.λz.xz(yz)
# K = λx.λy.x
# i = λc.cSK
#
# i, *ii, *i*ii, **ii*ii
# 0 100 10100 1100100 Iota is the encoding.
#
## (let iota ()
## (if (eq? #\* (read-char)) ((iota)(iota))
## (lambda (c) ((c (lambda (x) (lambda (y) (lambda (z) ((x z)(y z))))))
## (lambda (x) (lambda (y) x))))))
##
S = lambda x: lambda y: lambda z: x(z)(y(z))
K = lambda x: lambda y: x
i = lambda c: c(S)(K)
I = i(i)
def _decode(path):
bit, path = path[0], path[1:]
if bit == '0':
return i, path
A, path = _decode(path)
B, path = _decode(path)
return A(B), path
decode = lambda path: _decode(path)[0]
# K = *i*i*ii = 1010100
#
print K is i(i(i(i))) is decode('1010100')
# S = *i*i*i*ii = 101010100
#
print S is i(i(i(i(i)))) is decode('101010100')
# All of these return i itself.
print i is i
print i is i(i)(i)
print i is i( i ) ( i(i)(i) )
print i is i( i(i)(i) ) ( i )
print i is i( i(i)(i) ) ( i(i)(i) )
# Identity function
#
I is decode('100') # I.e. i(i)
|
