An idea for fast function composition

[castironpi at gmail.com]

On Feb 16, 3:47 pm, Arnaud Delobelle <arno... at googlemail.com> wrote:
> Hi all,
>
> Recently there was a thread about function composition in Python (and
> this was probably not the first).  The fast way to create a
> (anonymous) composite function
>
>      f1 o f2 o ... o fn
>
> in Python is via
>
>      lambda x: f1(f2(...fn(x)...)),
>
> but according to some this is neither the most compact nor the most
> readable.  Below I define a 'compose' function such that the above can
> be written
>
>      compose(f1, f2, ...., fn),
>
> the resulting function being as fast as the lambda version (or maybe
> faster?).  'getcomposer' is a helper function (which in most cases
> will amount to a dictionary lookup).
>
> ----------------------------------
> def getcomposer(nfunc, _cache={}):
>      "getcomposer(n) -> lambda f1, ..., fn:(lambda x: f1(...fn(x)...))"
>      try:
>          return _cache[nfunc]
>      except KeyError:
>          fnames = ['f%s' % i for i in range(nfunc)]
>          call = ''.join('%s(' % f for f in fnames)
>          args = ','.join(fnames)
>          cstr = 'lambda %s:(lambda x:%sx%s)' % (args, call, ')'*nfunc)
>          composer = _cache[nfunc] = eval(cstr)
>          return composer
>
> def compose(*functions):
>      "compose(f1, ..., fn) -> lambda x: f1(f2(...fn(x)...))"
>      return getcomposer(len(functions))(*functions)
>
> # Test
>
> def double(x): return 2*x
> def square(x): return x**2
> def succ(x): return x+1
>
> f1 = compose(double, square, succ, float)
> f2 = lambda x: double(square(succ(float(x))))
>
> def benchmark(f, n=1000000):
>      from time import time
>      from itertools import imap
>      t0 = time()
>      for _ in imap(f1, xrange(n)): pass
>      t1 = time()
>      return t1-t0
>
> print 'compose', benchmark(f1)
> print 'lambda ', benchmark(f2)
> ----------------------------------
>
> marigold:python arno$ python -i simple_compose.py
> compose 1.84630298615
> lambda  1.86365509033
>  >>> import dis
>  >>> dis.dis(f1)
>    1           0 LOAD_DEREF               0 (f0)
>                3 LOAD_DEREF               3 (f1)
>                6 LOAD_DEREF               1 (f2)
>                9 LOAD_DEREF               2 (f3)
>               12 LOAD_FAST                0 (x)
>               15 CALL_FUNCTION            1
>               18 CALL_FUNCTION            1
>               21 CALL_FUNCTION            1
>               24 CALL_FUNCTION            1
>               27 RETURN_VALUE
>  >>> dis.dis(f2)
>   23           0 LOAD_GLOBAL              0 (double)
>                3 LOAD_GLOBAL              1 (square)
>                6 LOAD_GLOBAL              2 (succ)
>                9 LOAD_GLOBAL              3 (float)
>               12 LOAD_FAST                0 (x)
>               15 CALL_FUNCTION            1
>               18 CALL_FUNCTION            1
>               21 CALL_FUNCTION            1
>               24 CALL_FUNCTION            1
>               27 RETURN_VALUE
>
> f1 and f2 are almost exaclty the same but array lookups (LOAD_DEREFs)
> in f1 replace dictionary lookups (LOAD_GLOBALs) in f2.  A C version of
> 'compose' could easily be written that doesn't require the use of a
> python lambda-function (as created by 'getcomposer').
>
> --
> Arnaud

def compose( funcs ):
   def reccompose( *args ):
      return compose( funcs[:-1] )( funcs[-1]( *args ) ) if funcs else
funcs[0]( *args )
   return reccompose