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.

Tweet

The original post was in the categories: python algorithms combinatory_python but I'm still in the process of migrating categories over.

The original post had **5 comments** I'm in the process of migrating over.