Y-conbinator in Python

[gamous]

Build recursive tools from scratch.

#Q: How to recurse in lambda calculus?

#Lets start with the Fibonacci function.

fact0=lambda n: 1 if n==0 else n*fact0(n-1)
print(fact0(10))
#Q: How to call fact0 in lambda fact0 without name?

self_fact=lambda self,n: 1 if n==0 else n*self(n-1)
#Q: What is function self?

fact1=lambda self,n: 1 if n==0 else n*self(self,n-1)
print(fact1(fact1,10))
#Q: How to let fact1 have only one parameter?

fact2=lambda self:lambda n: 1 if n==0 else n*self(self)(n-1)
print(fact2(fact2)(10))
#Q: How to call this function directly?

fact3=(lambda self:lambda n: 1 if n==0 else n*self(self)(n-1))(lambda self:lambda n: 1 if n==0 else n*self(self)(n-1))
print(fact3(10))
#Q: How to generalize this functor?

fact4=lambda self:lambda n: (lambda f:lambda m:1 if m==0 else m*f(n-1))(self(self))(n)
print(fact4(fact4)(10))
#Q: Is funciton f in fact4 equal to self_fact?

fact5=lambda self:lambda n: self_fact(self(self),n)
print(fact5(fact5)(10))
#So... Is self equivalent to self(self) ?!
#Q: How to extract self_fact as a parameter?

Y0=lambda f:(lambda self:lambda n: f(self(self),n))(lambda self:lambda n: f(self(self),n))
fact6=Y0(self_fact)(10)
print(fact6(10))
#Q: How to let all lambda have only one parameter?

Y = lambda f: (lambda self: f(self(self)))(lambda self: f(lambda y: self(self)(y)))
fact = Y(lambda self: lambda n: 1 if n==0 else n*self(n-1))
print(fact(10))
#That's the answer -- Y-conbinator.
# $ Y=λf.(λx.f(xx))(λxf(xx)) $ Found by Haskell Curry

#Q: How to generalize to multiparameter functions?
Z = lambda f: (lambda self: f(self(self)))(lambda self: f(lambda *y: self(self)(*y)))
#Z-conbinator.

#ref: https://www.functor.me/post/programming/y-combinator

[gamous]

Assemble a one-line base conversion function using the Y combinator.

from functools import reduce

chr_num_map=lambda x:x-87 if x>96 else x-55 if x>64 else x-48
out_num_map=lambda x:chr(x+48 if x<10 else x+87)
chr_raw_map=lambda x:x
out_raw_map=lambda x:chr(x)
out_base64_map=lambda x:"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"[x]
chr_base64_map=lambda x:b"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/".index(x)

def base_convert(data,in_base,out_base,chr_map=chr_num_map,ord_map=out_num_map):
    num=reduce(lambda r,x:r*in_base+x,map(lambda c:(chr_map)(ord(c)),data)) #foldl
    format_num=lambda r,n:(r if len(r)>0 else[0]) if n==0 else format_num([n%out_base]+r,n//out_base) #unfold
    return "".join(map(ord_map, format_num([],num))) #render

def base64_encode(data):
    return base_convert(data,256,64,chr_raw_map,out_base64_map)

def base64_decode(data):
    return base_convert(data,64,256,chr_base64_map,out_raw_map)

print(base64_decode("Z2Ftb3Vz"))

#y-conbinator version
fp_base=lambda data,in_base,out_base:"".join(map(lambda x:chr(x+48 if x<10 else x+87),\
    (lambda f:(lambda self:lambda r,n: f(self(self),r,n))(lambda self:lambda r,n: f(self(self),r,n)))\
        (lambda self,r,n:(r if len(r)>0 else[0]) if n==0 else self([n%out_base]+r,n//out_base))\
            ([],reduce(lambda r,x:r*in_base+x,map(lambda c:(lambda x:x-87 if x>96 else x-55 if x>64 else x-48)(ord(c)),data)))))
print(fp_base("a",16,10))