Composing functions in python

It doesn't work because all the anonymous functions you create in the loop refer to the same loop variable and therefore share its final value.

As a quick fix, you can replace the assignment with:

final = lambda x, f=f, final=final: f(final(x))

Or, you can return the lambda from a function:

def wrap(accum, f):
    return lambda x: f(accum(x))
...
final = wrap(final, f)

To understand what's going on, try this experiment:

>>> l = [lambda: n for n in xrange(10)]
>>> [f() for f in l]
[9, 9, 9, 9, 9, 9, 9, 9, 9, 9]

This result surprises many people, who expect the result to be [0, 1, 2, ...]. However, all the lambdas point to the same n variable, and all refer to its final value, which is 9. In your case, all the versions of final which are supposed to nest end up referring to the same f and, even worse, to the same final.

The topic of lambdas and for loops in Python has been already covered on SO.

The easiest approach would be first to write a composition of 2 functions:

def compose2(f, g):
    return lambda *a, **kw: f(g(*a, **kw))

And then use reduce to compose more functions:

import functools

def compose(*fs):
    return functools.reduce(compose2, fs)

Or you can use some library, which already contains compose function.

def compose (*functions):
    def inner(arg):
        for f in reversed(functions):
            arg = f(arg)
        return arg
    return inner

Example:

>>> def square (x):
        return x ** 2
>>> def increment (x):
        return x + 1
>>> def half (x):
        return x / 2

>>> composed = compose(square, increment, half) # square(increment(half(x)))
>>> composed(5) # square(increment(half(5))) = square(increment(2.5)) = square(3.5) = 12,25
12.25