First Success With Combinatory Python

In More Questions on the Path to Combinatory Python I wondered how to write an 'add' function such that not only

(add)(2)(2) == 4

worked but also things like:

(add)(add)(1)(2)(3) == 6
(add)(1)(add)(2)(3) == 6

If we throw in a unary function like 'neg' then things like this should work too:

(neg)(5) == -5
(neg)(neg)(5) == 5
(add)(3)(neg)(2) == 1

Here's how I started to think about it. An expression such as (add)(2)(2) could be described as having the signature "200". It consists of subexpressions requiring, respectively 2, 0 and 0 arguments. Just (add)(2) would have a signature "20" which is equivalent to a signature of 1.

Using this notion:

• (add)(add)(1)(2)(3) has signature 22000
• (add)(1)(add)(2)(3) has signature 20200
• (neg)(5) has signature 10
• (neg)(neg)(5) has signature 110
• (add)(3)(neg)(2) has signature 2010

It is easy to see that for an expression to be complete (i.e. not partial) it must have a signature ending in 0. But there is slightly more to it that than. Basically, start off with a score of 1 and work from left to write, every "2" you encounter increases the score by 1 and every "0" decreases it by 1. A "1" has no effect. When you hit a score of 0 you're complete.

Every complete signature has a particular bracketing of function application. For example, expressions of signature 112100 can be evaluated as follows:

def eval112100(a, b, c, d, e, f):
    return a(b(c(d(e))(f)))

and each partial signature has a function that can dispatch evaluation to another function depending on the number of args the next arg takes (relying on a function like add being annotated with add.args = 2).

def eval1121(a, b, c, d):
    return lambda e: (
        eval11210 if e.args == 0 else
        eval11211 if e.args == 1 else
        eval11212 if e.args == 2 else
        ...
    )(a, b, c, d, e)

I was still struggling to implement this in a recursive way that could handle unlimited depth and then I saw in a comment that Eric Wald came up with a solution:

def combinatoric(n):
    def decorator(f):
        @wraps(f)
        def wrapper(x):
            if callable(x):
                return lambda y: combinatoric(n)(f)(x(y))
            elif n > 1:
                return combinatoric(n - 1)(wraps(f)(partial(f, x)))
            else:
                return f(x)
        return wrapper
    return decorator

and so you then say

@combinatoric(1)
def neg(x):
    return -x

@combinatoric(2)
def add(x, y):
    return x + y

and it all works. The use of wraps is optional but including it means partial add will have the name add not wrapper.

As Eric points out in his comment, this still doesn't solve the (add)(M)(5) issue but I have some thoughts on that for a subsequent post.