Composing functions in python

Question

I have an array of functions and I'm trying to produce one function which consists of the composition of the elements in my array. My approach is:

def compose(list):
    if len(list) == 1:
        return lambda x:list[0](x)
    list.reverse()
    final=lambda x:x
    for f in list:
        final=lambda x:f(final(x))
    return final

This method doesn't seems to be working, help will be appreciated.

(I'm reversing the list because this is the order of composition I want the functions to be)

Biogeography

Answer 1

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.

Ammonify

Thanks for the answer, it indeed worked for me. I used the second method. Can you explain what do you mean by "final closures refer to the same f cell", and also can you please explain the first method. – Biogeography

Here's an interesting alternative. Replace l with l = [lambda x=n: x for n in range(10)] This produces [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] as one might expect. – Southward

@Southward That's the gist of the "quick fix" proposed near the beginning of the answer. In that pattern the convention is to name the keyword the same as the variable you are capturing, e.g. lambda n=n: .... – Ammonify

Answer 2

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.

Materi

This is going to create a shadow function for every function in fs. I don’t know how much functions in Python are resource intensive, but that seems wasteful. Instead, see other solution by Imanol Luengo: def compose(*funcs): return lambda x: reduce(lambda acc, f: f(acc), funcs, x) (https://mcmap.net/q/377961/-composing-functions-in-python) – Lasalle

You can bench it, but your solution will be probably slower. For most common case of 2 functions mine is zero cost. – Materi

reduce is functools.reduce in python3 – Faceless

Mind that compose(a,b,c) will result in the following order a(b(c(input))) – Siriasis

If you want no dependencies the 2 functions solution can be generalized with recursion: https://mcmap.net/q/377961/-composing-functions-in-python – Lillylillywhite

Answer 3

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

Inhibit

Can you show how (/is it even possible) to add an aggregation step - presuming the chained functions are operating on collections? – Navigate

@javadba I’m not sure what you mean. Can you give an example for what you would like to do? – Inhibit

Consider the functions might be : (add 5 to x, mult by 3, *find top 3*, *sum*) . the "top3" and "sum" are aggregations that I don't know how to insert into the composition. – Navigate

@javadba You could surely do that, although I would say that it looks a bit complicated then: compose(sum, lambda x: sorted(x, reverse=True)[:3], lambda x: map(lambda y: y * 3, x), lambda x: map(lambda y: y + 5, x)) – You could also just map once with a composed function: compose(sum, lambda x: sorted(x, reverse=True)[:3], lambda x: map(compose(lambda y: y * 3, lambda y: y + 5), x)). So if you named them nicely, it could look like this: compose(sum, top3, lambda x: map(compose(times3, plus5), x)). You could also get rid of that lambda by using functools.partial. – Inhibit

Answer 4

One liner:

compose = lambda *F: reduce(lambda f, g: lambda x: f(g(x)), F)

Example usage:

f1 = lambda x: x+3
f2 = lambda x: x*2
f3 = lambda x: x-1
g = compose(f1, f2, f3)
assert(g(7) == 15)

Aschim

Answer 5

Recursive implementation

Here's a fairly elegant recursive implementation, which uses features of Python 3 for clarity:

def strict_compose(*funcs):
    *funcs, penultimate, last = funcs
    if funcs:
        penultimate = strict_compose(*funcs, penultimate)
    return lambda *args, **kwargs: penultimate(last(*args, **kwargs))

Python 2 compatible version:

def strict_compose2(*funcs):
    if len(funcs) > 2:
        penultimate = strict_compose2(*funcs[:-1])
    else:
        penultimate = funcs[-2]
    return lambda *args, **kwargs: penultimate(funcs[-1](*args, **kwargs))

This is an earlier version which uses lazy evaluation of the recursion:

def lazy_recursive_compose(*funcs):
    def inner(*args, _funcs=funcs, **kwargs):
        if len(_funcs) > 1:
            return inner(_funcs[-1](*args, **kwargs), _funcs=_funcs[:-1])
        else:
            return _funcs[0](*args, **kwargs)
    return inner

Both would seem to make a new tuple and dict of arguments each recursive call.

Comparison of all suggestions:

Let's test some of these implementations and determine which is most performant, first some single argument functions (Thank you poke):

def square(x):
    return x ** 2

def increment(x):
    return x + 1

def half(x):
    return x / 2

Here's our implementations, I suspect my iterative version is the second most efficient (manual compose will naturally be fastest), but that may be in part due to it sidestepping the difficulty of passing any number of arguments or keyword arguments between functions - in most cases we'll only see the trivial one argument being passed.

from functools import reduce

def strict_recursive_compose(*funcs):
    *funcs, penultimate, last = funcs
    if funcs:
        penultimate = strict_recursive_compose(*funcs, penultimate)
    return lambda *args, **kwargs: penultimate(last(*args, **kwargs))

def strict_recursive_compose2(*funcs):
    if len(funcs) > 2:
        penultimate = strict_recursive_compose2(*funcs[:-1])
    else:
        penultimate = funcs[-2]
    return lambda *args, **kwargs: penultimate(funcs[-1](*args, **kwargs))

def lazy_recursive_compose(*funcs):
    def inner(*args, _funcs=funcs, **kwargs):
        if len(_funcs) > 1:
            return inner(_funcs[-1](*args, **kwargs), _funcs=_funcs[:-1])
        else:
            return _funcs[0](*args, **kwargs)
    return inner

def iterative_compose(*functions):
    """my implementation, only accepts one argument."""
    def inner(arg):
        for f in reversed(functions):
            arg = f(arg)
        return arg
    return inner

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

def reduce_compose1(*fs):
    return reduce(_compose2, fs)

def reduce_compose2(*funcs):
    """bug fixed - added reversed()"""
    return lambda x: reduce(lambda acc, f: f(acc), reversed(funcs), x)

And to test these:

import timeit

def manual_compose(n):
    return square(increment(half(n)))

composes = (strict_recursive_compose, strict_recursive_compose2, 
            lazy_recursive_compose, iterative_compose, 
            reduce_compose1, reduce_compose2)

print('manual compose', min(timeit.repeat(lambda: manual_compose(5))), manual_compose(5))
for compose in composes:
    fn = compose(square, increment, half)
    result = min(timeit.repeat(lambda: fn(5)))
    print(compose.__name__, result, fn(5))

Results

And we get the following output (same magnitude and proportion in Python 2 and 3):

manual compose 0.4963762479601428 12.25
strict_recursive_compose 0.6564744340721518 12.25
strict_recursive_compose2 0.7216697579715401 12.25
lazy_recursive_compose 1.260614730999805 12.25
iterative_compose 0.614982972969301 12.25
reduce_compose1 0.6768529079854488 12.25
reduce_compose2 0.9890829260693863 12.25

And my expectations were confirmed: the fastest is of course, manual function composition followed by the iterative implementation. The lazy recursive version is much slower - likely since a new stack frame is created by each function call and a new tuple of functions is created for each function.

For a better and perhaps more realistic comparison, if you remove **kwargs and change *args to arg in the functions, the ones that used them will be more performant, and we can better compare apples to apples - here, aside from manual composition, reduce_compose1 wins followed by the strict_recursive_compose:

manual compose 0.443808660027571 12.25
strict_recursive_compose 0.5409777010791004 12.25
strict_recursive_compose2 0.5698030130006373 12.25
lazy_recursive_compose 1.0381018499610946 12.25
iterative_compose 0.619289995986037 12.25
reduce_compose1 0.49532539502251893 12.25
reduce_compose2 0.9633988010464236 12.25

Functions with just one arg:

def strict_recursive_compose(*funcs):
    *funcs, penultimate, last = funcs
    if funcs:
        penultimate = strict_recursive_compose(*funcs, penultimate)
    return lambda arg: penultimate(last(arg))

def strict_recursive_compose2(*funcs):
    if len(funcs) > 2:
        penultimate = strict_recursive_compose2(*funcs[:-1])
    else:
        penultimate = funcs[-2]
    return lambda arg: penultimate(funcs[-1](arg))

def lazy_recursive_compose(*funcs):
    def inner(arg, _funcs=funcs):
        if len(_funcs) > 1:
            return inner(_funcs[-1](arg), _funcs=_funcs[:-1])
        else:
            return _funcs[0](arg)
    return inner

def iterative_compose(*functions):
    """my implementation, only accepts one argument."""
    def inner(arg):
        for f in reversed(functions):
            arg = f(arg)
        return arg
    return inner

def _compose2(f, g):
    return lambda arg: f(g(arg))

def reduce_compose1(*fs):
    return reduce(_compose2, fs)

def reduce_compose2(*funcs):
    """bug fixed - added reversed()"""
    return lambda x: reduce(lambda acc, f: f(acc), reversed(funcs), x)

Amersham

can you do an async one? – Herisau

Answer 6

The most reliable implementation I have found is in the 3rd party library toolz. The compose function from this library also deals with docstring for the composition of functions.

The source code is freely available. Below is a simple example of usage.

from toolz import compose

def f(x):
    return x+1

def g(x):
    return x*2

def h(x):
    return x+3

res = compose(f, g, h)(5)  # 17

Casaleggio

Answer 7

You can also create an array of functions and use reduce:

from functools import reduce


def f1(x): return x+1
def f2(x): return x+2
def f3(x): return x+3

x = 5

# Will print f3(f2(f1(x)))
print(reduce(lambda acc, x: x(acc), [f1, f2, f3], x))

# As a function:
def compose(*funcs):
    return lambda x: reduce(lambda acc, f: f(acc), funcs, x)

f = compose(f1, f2, f3)

Zingaro

Can you show how (/is it even possible) to add an aggregation step - presuming the chained functions are operating on collections? – Navigate

Answer 8

pip install funcoperators is another library to implement it that allows infix notation:

from funcoperators import compose

# display = lambda x: hex(ord(list(x)))
display = hex *compose* ord *compose* list

# also works as a function
display = compose(hex, ord, list)

pip install funcoperators https://pypi.org/project/funcoperators/

Disclaimer: I'm the creator of the module

Brat

Answer 9

Suppose you have the following functions:

def square(x): 
    return x**2

def inc(x): 
    return x+1

def half(x): 
    return x/2

Define a compose function as follows:

import functools

def compose(*functions):
    return functools.reduce(lambda f, g: lambda x: g(f(x)),
                            functions,
                            lambda x: x)

Usage:

composed = compose(square, inc, inc, half)
compose(10)
>>> 51.0

which executes the functions procedurally in the defined order:

1. square (= 100)
2. inc (= 101)
3. inc (= 102)
4. half (= 51)

Adapted from https://mathieularose.com/function-composition-in-python/.

Downe

This is interesting to me because of the procedural execution - however (in python 3) on print(compose(10)) I get: <function compose.<locals>.<lambda>.<locals>.<lambda> at 0x000002E51BF3FDC0> I'm not sure what I need to do to get the value. – Ezana

Answer 10

I prefer this one due to readability/simplicity

from functools import reduce

def compose(*fs):
   apply = lambda arg, f: f(arg)
   composition = lambda x: reduce(apply, [x, *fs])
   return composition

the pipe = compose(a, b, c) will first apply a, then b and then c.

With regard to maintainability (an debugging) I think actually this one is the easiest to use:

def compose(*fs):
    def composition(x):
        for f in fs:
            x = f(x)
        return x
    return composition

Siriasis

Answer 11

You can use funcy.

Installation:

pip install funcy

Then you can use compose or rcompose as follows:

from funcy import compose, rcompose

def inc(x): return x + 1
def double(x): return x + x
def tripple(x): return x + x + x

print(compose(tripple, double, inc)(1)) # 12
print(rcompose(inc, double, tripple)(1)) # 12

Variegated

Funny enough, the author of funcy already wrote the currently top-rated answer on this question, but does not mention funcy in their answer (their answer uses the same implementation as funcy though, last I looked). – Kalman

Answer 12

I found this piece of code from GeeksforGeeks here for Python 3. Not sure of how efficient it is, but it is very simple to understand.

# importing reduce() from functools 
from functools import reduce

# composite_function accepts N 
# number of function as an 
# argument and then compose them 
def composite_function(*func): 
    
    def compose(f, g): 
        return lambda x : f(g(x)) 
            
    return reduce(compose, func, lambda x : x) 

# Function to add 2 
def add(x): 
    return x + 2

# Function to multiply 2 
def multiply(x): 
    return x * 2

# Function to subtract 2 
def subtract(x): 
    return x - 1

# Here add_subtract_multiply will 
# store lambda x : multiply(subtract(add(x))) 
add_subtract_multiply = composite_function(multiply, 
                                        subtract, 
                                        add) 

print("Adding 2 to 5, then subtracting 1 and multiplying the result with 2: ", 
    add_subtract_multiply(5)) 

You can keep adding more functions to composite_functions e.g.:

print(composite_function(multiply, add, subtract, multiply,subtract, add)(5))

Ezana

Answer 13

More general solution of Imanol Luengo from my point of view (python notebook example):

from functools import reduce
from functools import partial

def f(*argv, **kwargs):
  print('f: {} {}'.format(argv, kwargs))
  return argv, kwargs

def g(*argv, **kwargs):
  print('g: {} {}'.format(argv, kwargs))
  return argv, kwargs

def compose(fs, *argv, **kwargs):
  return reduce(lambda x, y: y(*x[0], **x[1]), fs, (argv, kwargs))

h = partial(compose, [f, g])
h('value', key='value')
output:
f: ('value',) {'key': 'value'}
g: ('value',) {'key': 'value'}

m = partial(compose, [h, f, g])
m('value', key='value')
output:
f: ('value',) {'key': 'value'}
g: ('value',) {'key': 'value'}
f: ('value',) {'key': 'value'}
g: ('value',) {'key': 'value'}

Treasonable

Answer 14

Perfectly good question, but the answers sure are unnecessarily complex. It's just:

def compose(*funs):
    return (lambda x:
        x if len(funs) == 0
         else compose(*funs[:-1])(funs[-1](x)))

Lianeliang

This solution cannot be adapted to cases for arbitrary arguments (i.e., *args, **kwargs) because return *args is a syntax error. – Parrott

Answer 15

If you want no dependencies here is a one-liner recursive solution:

def compose(*f):
    return f[0] if len(f) <= 1 else lambda *a,**kw: f[0](compose(*f[1:])(*a,**kw))

N.B. len(f) == 1 might seem more reasonable at first sight, but it allows to write compose() (i.e. no arguments) throwing an error only when you apply the empty compose function. On the contrary, with len(f) <= 1, compose() throws an error immediately, which is a more rational behavior.

Lillylillywhite

Does this solution work? def compose(*f): return f[0] if len(f) <= 1 else lambda *a,**kw: f[0](compose(*f[1:])(*a,**kw)) def squares(*args): return (x**2 for x in args) assert compose(squares, sum, lambda x: x == 36)(3, 3, 3, 3) raises TypeError: <lambda>() takes 1 positional argument but 4 were given for me. – Parrott

Nevermind: it fails because I put the function in the wrong order. – Parrott

Answer 16

This is my version

def compose(*fargs):
    def inner(arg):
        if not arg:
            raise ValueError("Invalid argument")
        if not all([callable(f) for f in fargs]):
            raise TypeError("Function is not callable")
        return reduce(lambda arg, func: func(arg), fargs, arg)
    return inner

An example of how it's used

def calcMean(iterable):
    return sum(iterable) / len(iterable)


def formatMean(mean):
    return round(float(mean), 2)


def adder(val, value):
    return val + value


def isEven(val):
    return val % 2 == 0

if __name__ == '__main__':
    # Ex1

    rand_range = [random.randint(0, 10000) for x in range(0, 10000)]

    isRandIntEven = compose(calcMean, formatMean,
                            partial(adder, value=0), math.floor.__call__, isEven)

    print(isRandIntEven(rand_range))

Homs

This is going to throw an error if arg evaluates to false. For example, if 0 is the value of arg. – Parrott