## Thursday, August 27, 2015

### n-ary functions and argument lists

Suppose we have a binary operation `Op2 = (lambda (left right) ...)`. If it is closed over some type, you can make expression trees.
```(Op2 (Op2 <arg1> <arg2>)
(Op2
(Op2 <arg3> <arg4>)
<arg5>))```
If `Op2` is associative as well, these are equal:
```(Op2 (Op2 <arg1> <arg2>)
(Op2 <arg3>
(Op2 <arg4> <arg5>)))

(Op2 <arg1>
(Op2 (Op2 <arg2> <arg3>)
(Op2 <arg4> <arg5>)))```

This makes the tree structure irrelevant so long as the fringe of the tree stays in order, so we can flatten the tree by making an N-ary version of the binary operation:
```(define (binary->nary Op2)
(lambda (a1 a2 . an)
(fold-left Op2 (Op2 a1 a2) an)))

((binary->n-ary Op2) <arg1> <arg2> <arg3> <arg4> <arg5> <arg6> etc.)```
The value of this expression naturally depends upon the values of the arguments. Changing the argument list is highly likely to change the value of the entire expression. However, we can make certain changes to the argument list without changing the value of the entire expression. If we know what those changes are, we can manipulate the argument list before invoking the operator, and still get the same answer. Naturally, most of the changes we can make to the argument list depend on the specifics of `Op2`, but it turns out that some interesting changes are possible without knowing any specifics, only knowing a few high-level properties of `Op2`.

Obviously, the first thing we can do is reduce the argument list through evaluation. Simply replace the first two arguments with the value of `(Op2 <arg1> <arg2>)`
```((binary->n-ary Op2) <arg1> <arg2> <arg3> <arg4> <arg5> <arg6> etc.) =

((binary->n-ary Op2) (Op2 <arg1> <arg2>) <arg3> <arg4> <arg5> <arg6> etc.) =

((binary->n-ary Op2) <result> <arg3> <arg4> <arg5> <arg6> etc.)```
Since `Op2` is associative, we can replace any 2 adjacent arguments with their combination.

Now suppose there is an identity element among the arguments we can give to Op2.
```(Op2 <arg> id) = <arg>  and
(Op2 id <arg>) = <arg>```
We can do this:
```(define (binary->nary Op2)
(lambda an
(fold-left Op2 id an)))

(define Op (binary->nary Op2))```
Which is cleaner than the original. We also get a new way to manipulate the argument list to `Op`. We can add the identity element anywhere we wish, or we can delete the identity element wherever we find one.
```(Op <arg1> <arg2> <arg3> Id <arg4> <arg5> <arg6> etc.) =

(Op <arg1> <arg2> <arg3> <arg4> <arg5> <arg6> etc.) =

(Op <arg1> Id <arg2> <arg3> <arg4> <arg5> Id <arg6> etc.)```

One more restriction. We want `Op2` to be invertible. Suppose `(Op2 <arg1> <arg2>) = <result>`. `Op2` is invertible if, given any two of <arg1>, <arg2>, and <result>, the third can be uniquely determined. If you have one <arg> and a <result>, you can run things backwards and get the other <arg>.

Requiring `Op2` to be invertible has many consequences, some of them quite non-obvious. An obvious consequence, though, is that we can define inverse elements. If `(Op2 <argA> <argB>) = Id`, then we say that <argB> is the inverse of <argA> (and vice versa). We find the inverse of an argument by fixing the output as the identity element and running `Op2` backwards to find the other argument.

This gives us the final way to manipulate the argument list. If an element appears next to its inverse, both can be removed:
```(Op <arg1> <arg2> <arg3> (inverse <arg3>) <arg5> <arg6> etc.) =
(Op <arg1> <arg2> (Op2 <arg3> (inverse <arg3>)) <arg5> <arg6> etc.) =
(Op <arg1> <arg2> Id <arg5> <arg6> etc.) =
(Op <arg1> <arg2> <arg5> <arg6> etc.)```

So here are all the restrictions on Op2:
• Closed over an set of arguments
• Associative
• Has an identity argument
• Invertible
If `Op2` has these properties (and a lot of binary operations do), then we can define an n-ary `Op` and play with its argument list. If you do this, you might notice that it looks kind of familiar:
`(op f g (inverse g) j id h) = (op f j id h) = (op f j h)`

The argument list sort of looks like a function pipeline. The allowed manipulations of the argument list are compatible with a function pipeline, too. In fact, it could be a function pipeline if `Op` is the `compose` operator, and `f`, `g`, and `h` are appropriate invertible unary functions. But whatever it is, the point is that it looks enough like a function pipeline that we can pretend that it is.