Implement clojure-a-like comp() function in python3

Question

With a friend some time ago we wanted to write our own implementation of comp() clojure function in python3. we ended up writing the following function:

 def comp(*fs): 
 """
 Takes a set of functions and returns a fn that is the 
 composition of those fns. The returned fn takes a variable number of args,
 applies the rightmost of fns to the args, the next fn (right-to-left) to
 the result, etc.
 """
 if len(fs) == 1:
 return lambda *x: fs[0](*x)
 else:
 return lambda *x: fs[0](comp(*fs[1:])(*x))

In my oppinion it's still opaque and difficult to read. But it works as in:

 # Checking for single argument
 >>> [comp(lambda x: x*10,lambda x: x+2, lambda x: x*3, lambda x: x+3)(x) for x in range(6)]
 [110, 140, 170, 200, 230, 260]
 # Checking for multiple arguments
 >>> a = lambda x: sum(x)
 >>> b = lambda x, y, z: [x*1, y*2, z*3]
 >>> comp(a, b)(1, 2, 3)
 14

How could it be written better?

Answer 1

Your approach has one serious drawbacks: it creates N-1 new bound function instances on every invocation of the returned function with an argument length of N if big-O performance guarantees are relevant to you. To avoid this you can either use a loop or the reduce operation, both of which only create a fixed number of function instances (that doesn't depend on the number of functions to chain).

Additionally I believe that both variants are easier to understand than the code in your question because it doesn't rely on recursion.

Loop

def comp_loop(*fns):
 def comped(*x):
 for fn in reversed(fns):
 x = fn(*x)
 return x
 if len(fns) == 0:
 return lambda *x: x
 if len(fns) == 1:
 return fns[0]
 return comped

Reduce

from functools import reduce
def comp_reduce(*fns):
 if len(fns) == 0:
 return lambda *x: x
 if len(fns) == 1:
 return fns[0]
 return lambda *x: reduce(lambda accum, fn: fn(*accum), reversed(fns), x)

• user151023: Thx for the detailed answer! It's very precise and it offers variety of implementations!