I saw this on a job ad (on SO):
lambda f: (lambda a: a(a))(lambda b: f(lambda *args: b(b)(*args)))
So what I understand is it is an anonymous (unnamed) function, which is composed of two further nested anonymous functions. The innermost function takes a variable list of arguements (*args).
I can't work out what is it supposed to do. Is this something that would actually work or is it impossible to tell without seeing the actual list of args?
I've undone the lambdas just to make it a little easier to read. Here's the code using nested functions:
def f1(f):
def f2(a):
return a(a)
def f3(b):
def f4(*args):
return b(b)(*args)
return f(f4)
return f2(f3)
This would be equivalent basically to:
f1 = lambda f: (lambda a: a(a))(lambda b: f(lambda *args: b(b)(*args)))
Now let's follow the function calls. First you're going to call f1 with some argument. Then the following is going to happen:
Therefore f1 can be reduced to:
def f1(f):
def f3():
def f4(*args):
return f3()(*args)
return f(f4)
return f3()
Now I've come up with a way to call f1 that doesn't end in infinite recursion:
called = False
def g1(func):
def g2(*args):
print args
return None
global called
if not called:
called = True
func(5)
else:
return g2
f1(g1) # prints "(5,)"
As you can see, it uses a global to stop the recursion.
Here's another example that runs trials of a Poisson distribution with lambda (lambda is a parameter to the Poisson distribution, not the lambda operator) of 10:
import random
def g3(func):
def g4(a):
def g5(b):
print a
return a+b
return g5
if random.random() < 0.1:
return g4(1)
else:
return g4(func(1))
f1(g3)
And finally something deterministic, not depending on a global, and actually somewhat interesting:
def g6(func):
def g7(n):
if n > 0:
return n*func(n-1)
else:
return 1
return g7
print f1(g6)(5) # 120
print f1(g6)(6) # 720
I'm sure everyone can guess what this function is, but pretty interesting that you can actually get this strange lambda expression to do something useful.
The code is creating Y-combinator in Python. This is merely an excercise, not a real world code; don't try to decrypt it.
To understand what Y-combinator itself does, you may refer to this SO question: What is a y-combinator? and to its wikipedia page: Fixed-point combinator.
Maybe this ad is looking for people that know functional programming and/or advanced computer science topics like Lambda calculus and Combinatory logic, which are primary theoretical foundation behind functional programming.
Or maybe their company is Y Combinator winner startup, and they are merely looking for Python programmers with CS background.
Not just *args, it's hard to tell what it is without knowing what a, b, f, and *args are.
The rabbit hole goes especially deep when b is passed as argument to function b, and that result is a function to which args is passed.
This is quite equivalent, without too much nesting:
def f1(f):
def f2(a): return a(a)
def f3(b):
def f4(*args): return b(b)(*args)
return f(f4)
return f2(f3)
f2 can be replaced, so we get
def f1(f):
def f3(b):
def f4(*args): return b(b)(*args)
return f(f4)
return f3(f3) # was f2(f3)
f3 is always called with itself, so we replace b with f3:
def f1(f):
def f3():
def f4(*args): return f3()(*args)
return f(f4)
return f3()
So what does it do?
We see f3() returns whatever f returns, and this is supposed to be called with an arbitrary number of arguments.
f is supposed to take a function taking another function with *args and returning such a function.
Calling f1(f) returns whatever f(f4) returns.
Let's test it:
f=lambda ff: lambda *args: ff(*args), f1(f)() gives us an infinite recursion.f=lambda ff: lambda *args: (ff, args) doesn't call the given function, so we can safely play with it:
f1(f)(4) gives us a tuple (f4, (4,)).f1(f)(4)[0](1), we get (f4, (1,)).