iterative lambda construction

[Steven Bethard]

markscottwright wrote:
> Just for the hell of it, I've been going through the old Scheme-based
> textbook "Structure and Interpretation of Computer Programs" and seeing
> what I can and can't do with python.  I'm trying to create a function
> that returns the function (not the results of the function, but a
> function object) that results from applying function f to it's (single)
> argument N times.  For example, if you have "def sq(x): return x*x",
> then repeated(sq, 2)(2) = 16, repeated(sq, 3)(2) = 256, etc.
> 
> I can do it recursively, like this:
> 
> def repeated(f, count):
>    if count == 1:
>        return f
>    else:
>        return lambda x: f(repeated(f, count - 1)(x)
> 
> But when I try to do it iteratively, it just hangs when I try to
> evaluate the results (for count > 1):
> 
> def repeated2(f, count):
>     newfun = f
>     for i in range(count-1):
>         newfun = lambda x: newfun(f(x))
>     return newfun
> 
> For the life of me, I can't figure out why.

Your problem is that lambdas (and defs) do late-binding.  Consider the 
following code:

py> newfun = (1).__add__
py> id(newfun)
18354384
py> newfun = lambda: sys.stdout.write('%s' % id(newfun))
py> id(newfun)
18217328
py> newfun()
18217328

Note that the id of 'newfun' is the same in the body of the lambda as 
the id of 'newfun' after the lambda is defined.  That is, if 'newfun' in 
the lambda were to be called, it would call the lambda function 
recursively, instead of calling the previous 'newfun'.  This is why 
you're getting infinite recursion.

The reason this happens is that, when a name is not bound by the 
argument list of a function, Python will look for that name in the 
enclosing scopes.  Since the lambda does not bind the name 'newfun', 
Python looks out to the enclosing scope to find 'newfun' (which, in this 
case, happens to be the funciton itself).

One solution to this problem is to bind the old function to a name in 
the argument list of your lambda[1]:

py> def repeated2(f, count):
...     newfun = f
...     for i in range(count - 1):
...         def newfun(x, oldfun=newfun):
...             return oldfun(f(x))
...     return newfun
...
py> def square(x):
...     return x**2
...
py> repeated2(square, 2)(2)
16
py> repeated2(square, 3)(2)
256

Another possibility would be to store the old function as part of a 
class instance:

py> class Composer(object):
...     def __init__(self, outerfunc, innerfunc):
...         self.outerfunc = outerfunc
...         self.innerfunc = innerfunc
...     def __call__(self, x):
...         return self.outerfunc(self.innerfunc(x))
...
py> def repeated2(f, count):
...     newfun = f
...     for _ in range(count - 1):
...         newfun = Composer(newfun, f)
...     return newfun
...
py> repeated2(square, 2)(2)
16
py> repeated2(square, 3)(2)
256

Note that either way, you need some means to store the old value of 
newfunc.  In the first case, it's stored by binding it as a default 
value of one of the the function's arguments.  In the second case, it's 
stored as an instance attribute of a class.

STeVe

[1] I use def instead of lambda.  See "Inappropriate use of Lambda" in 
http://www.python.org/moin/DubiousPython