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)