iterative lambda construction
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. -- http://mail.python.org/mailman/listinfo/python-list
Re: iterative lambda construction
markscottwright [EMAIL PROTECTED] writes: 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 -- http://mail.python.org/mailman/listinfo/python-list
Re: iterative lambda construction
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
--
http://mail.python.org/mailman/listinfo/python-list
Re: iterative lambda construction
On Mon, Feb 21, 2005 at 01:14:00PM -0800, Paul Rubin wrote: markscottwright [EMAIL PROTECTED] writes: 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 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 -- http://mail.python.org/mailman/listinfo/python-list
