RecursionError composing lambdas

Question

I am trying to write a function that composes any number of lambda functions.

I have two simple lambda functions.

f = lambda x: x + 1
g = lambda x: x**2

My attempt at a composing function is this:

def compose(*functions):
    composed = lambda x: x  # Function that returns input
    for function in reversed(functions):
        composed = lambda x: function(composed(x))
    return composed

My thinking was to loop through the variable number of functions, each time making the composed function include a new function inside it.

Then I could make a function that is a composition of f and g

c = compose(f, g)

So calling c(5) should return f(g(5)), which is 26. But instead, I get

RecursionError: maximum recursion depth exceeded

I thought introducing an intermediate variable might fix the problem.

def compose(*functions):
    composed = lambda x: x  # Function that returns input
    for function in reversed(functions):
        intermediate = lambda x: function(composed(x))
        composed = intermediate
    return composed

But the same error is raised.

Is there a way to fix this?

Answer 1

First, I think your approach will suffer from late closure binding, as function in lambda will only take the last value of function at the end of the iteration. Secondly, composed will only call itself recursively in the end also due to the first reason; composed - the lambda - calls the last value of composed - itself!

One possible fix is to bind composed and function to the lambda at each iteration:

def compose(*functions):
    composed = lambda x: x
    for function in reversed(functions):
        composed = lambda x, function=function, composed=composed: function(composed(x))
    return composed

print(compose(f, g)(5))
# 26

But your overall problem looks like a good use case for functools.reduce:

from functools import reduce

def compose(*functions):
    def inner(v):
        return reduce(lambda x, y: y(x),  reversed(functions), v)
    return inner

print(compose(f, g)(5))
# 26