recursive lambda-expressions possible?

Question

I'm trying to write a lambda-expression that calls itself, but i can't seem to find any syntax for that, or even if it's possible.

Essentially what I wanted to transfer the following function into the following lambda expression: (I realize it's a silly application, it just adds, but I'm exploring what I can do with lambda-expressions in python)

def add(a, b):
   if a <= 0:
      return b
   else:
      return 1 + add(a - 1, b)

add = lambda a, b: [1 + add(a-1, b), b][a <= 0]

but calling the lambda form of add results in a runtime error because the maximum recursion depth is reached. Is it even possible to do this in python? Or am I just making some stupid mistake? Oh, I'm using python3.0, but I don't think that should matter?

Answer 1

Maybe you need a Y combinator?

Edit - make that a Z combinator (I hadn't realized that Y combinators are more for call-by-name)

Using the definition of the Z combinator from Wikipedia

>>> Z = lambda f: (lambda x: f(lambda *args: x(x)(*args)))(lambda x: f(lambda *args: x(x)(*args)))

Using this, you can then define add as a completely anonymous function (ie. no reference to its name in its definition)

>>> add = Z(lambda f: lambda a, b: b if a <= 0 else 1 + f(a - 1, b))
>>> add(1, 1)
2
>>> add(1, 5)
6

Answer 2

First of all recursive lambda expressions are completely unnecessary. As you yourself point out, for the lambda expression to call itself, it needs to have a name. But lambda expressions is nothing else than anonymous functions. So if you give the lambda expression a name, it's no longer a lambda expression, but a function.

Hence, using a lambda expression is useless, and will only confuse people. So create it with a def instead.

But yes, as you yourself discovered, lambda expressions can be recursive. Your own example is. It's in fact so fantastically recursive that you exceed the maximum recursion depth. So it's recursive alright. Your problem is that you always call add in the expression, so the recursion never stops. Don't do that. Your expression can be expressed like this instead:

add = lambda a, b: a > 0 and (1 + add(a-1, b)) or b

Which takes care of that problem. However, your first def is the correct way of doing it.

Answer 3

add = lambda a, b: b if a <= 0 else 1 + add(a - 1, b)

Answer 4

Perhaps you should try the Z combinator, where this example is from:

>>> Z = lambda f: (lambda x: f(lambda *args: x(x)(*args)))(lambda x: f(lambda *args: x(x)(*args)))
>>> fact = lambda f: lambda x: 1 if x == 0 else x * f(x-1)
>>> Z(fact)(5)
120

Answer 5

You want the Y combinator, or some other fixed point combinator.

Here's an example implementation as a Python lambda expression:

Y = lambda g: (lambda f: g(lambda arg: f(f)(arg))) (lambda f: g(lambda arg: f(f)(arg)))

Use it like so:

factorial = Y(lambda f: (lambda num: num and num * f(num - 1) or 1))

That is, you pass into Y() a single-argument function (or lambda), which receives as its argument a recursive version of itself. So the function doesn't need to know its own name, since it gets a reference to itself instead.

Note that this does get tricky for your add() function because the Y combinator only supports passing a single argument. You can get more arguments by currying -- but I'll leave that as an exercise for the reader. :-)