iterative lambda construction

[markscottwright]

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. It seems like for count =
2, for example, the results from repeated2 should be lambda x: f(f(x)),
but it doesn't seem to be.

 

[Paul Rubin]

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. It seems like for count =
2, for example, the results from repeated2 should be lambda x: f(f(x)),
but it doesn't seem to be.

It's Python's scoping madness. Try:

def repeated2(f, count):
newfun = lambda x: x # identity
for i in range(count):
newfun = lambda x, g=newfun: g(f(x))
return newfun

 

[Andrew Koenig]

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

The trouble is that Python's scoping rules are subtly different from
Schemes, so you're binding to the wrong instance of newfun. You should do
this:

def repeated2(f, count):
newfun = f
for i in range(count-1):
newfun = lambda x, g=newfun: g(f(x))
return newfun

Alternatively, you could do it this way:

def repeated3(f, count):
def g(x):
for i in range(count):
x = f(x)
return x
return g

 

[Steven Bethard]

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

 

[Jack Diederich]

It's Python's scoping madness. Try:

def repeated2(f, count):
newfun = lambda x: x # identity
for i in range(count):
newfun = lambda x, g=newfun: g(f(x))
return newfun

Ahh, but not sufficienty evil or pernicious.

def evil(f, count):
def apply_evil(accum, func):
return func(accum)
def pernicious(x):
return reduce(apply_evil, [f]*count, x)
return pernicious

def f(x):
return x+x

print evil(f, 3)(2)

More seriously I'd go without the recursion and just make a wrapper
that applies the function count times in a wrapper.

def benign(f, count):
def wrap(x):
result = f(x)
for (i) in range(count-1):
result = f(result)
return result
return wrap

print benign(f, 3)(2)

-Jack