Black Magic - Currying using __get__

Michael Spencer mahs at telcopartners.com
Thu Mar 24 20:27:12 CET 2005


Wow - Alex Martelli's 'Black Magic' Pycon notes
http://www.python.org/pycon/2005/papers/36/pyc05_bla_dp.pdf

include this gem:
 > Functions 'r descriptors
 > def adder(x, y): return x + y
 >     add23 = adder.__get__(23)
 >     add42 = adder.__get__(42)
 > print add23(100), add42(1000)
 > 123 1042

This means that you can do (left) currying without a separate curry function
(Of course, google reveals that the idea has been discussed before,
http://mail.python.org/pipermail/python-dev/2003-October/038933.html)


Although it's less flexible than a general curry function, 'method currying' is 
much faster, e.g., compare two functions for tail-filtering an iterator:

def filtertail(op, iterable):
     """Recursively filter the tail of an iterator, based on its head
         Useful for succinct (though not very fast) implementations
         of sieve of eratosthenes among other"""
     iterator = iter(iterable)
     while 1:
         head = iterator.next()
         yield head
         iterator = it.ifilter(curry(op,Missing,head), iterator)

def filtertail2(op, iterable):
     """An alternative to filtertail, using Alex Martelli's observation
         that functions are descriptors.  Will not work for built-in
         functions that lack a __get__ method"""
     iterator = iter(iterable)
     opcurry = op.__get__
     while 1:
         head = iterator.next()
         yield head
         iterator = it.ifilter(opcurry(head), iterator)

using these generator functions, a Sieve of Eratosthenes can be written as:

primes = list(filtertail(operator.mod, xrange(2,N)))
or
primes = list(filtertail2(lambda head, tail: tail % head, xrange(2,N)))

but the second version, using 'method currying' is 4 times the speed, despite 
not using the stdlib operator.mod function

def timethem(N):
     import time
     t1 = time.clock()
     p = list(filtertail(op.mod, xrange(2,N)))
     t2 = time.clock()
     p = list(filtertail2(lambda head, tail: tail % head, xrange(2,N)))
     t3 = time.clock()
     return t2-t1, t3-t2

  >>> timethem(10000)
  (3.8331997502475588, 0.79605759949936328)
  >>> timethem(100000)
  (240.68151008019186, 61.818026872130304)
  >>>

of course, neither version is anywhere near the most efficient Python 
implementation - this is a comparison of currying, not sieving.


BTW, here's the curry function I used (it could probably be faster; I'm not sure 
what/where the future stdlib version is)


Missing = Ellipsis
def curry(*cargs, **ckwargs):
     fn, cargs = cargs[0], cargs[1:]
     if cargs[0] is Missing:
         while cargs[0] is Missing: # rightcurry
             cargs = cargs[1:]
         def call_fn(*fargs, **fkwargs):
             d = ckwargs.copy()
             d.update(fkwargs)
             return fn(*(fargs+cargs),**d)
         name = "%s(...,%s)" % (fn.__name__, ",".join(repr(i) for i in cargs))
     else:
         def call_fn(*fargs, **fkwargs):
             d = ckwargs.copy()
             d.update(fkwargs)
             return fn(*(cargs + fargs), **d)
         name = "%s(%s,...)" % (fn.__name__, ",".join(repr(i) for i in cargs))
     call_fn.func_name = name
     call_fn.curry = True
     return call_fn

Michael




More information about the Python-list mailing list