iterative lambda construction

[Andrew Koenig]

"markscottwright" <markscottwright at gmail.com> wrote in message 
news:1109018810.652908.93840 at f14g2000cwb.googlegroups.com...
> 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