Composition of a hierarchy of functions

Question

Is there a canonical way to express a function that is a composition of a rooted tree of functions?

Here is a concrete example of what I mean by "composition of a tree of functions." Take a rooted tree whose nodes are labelled by functions, like so:

Each function at a node is a composition of the functions at its child nodes. The function that is associated to the tree, itself, is the composition

F = a0(b0(c0(e0, e1, e2)), b1(d0(f0), d1(g0, g1)))

More explicitly, F is a function of 6 arguments that are evaluated by the functions at the leaves:

F(x0, ... , x5) == a0(b0(c0(e0(x0), e1(x1), e2(x2))),
                      b1(d0(f0(x3)), d1(g0(x4), g1(x5))))

General question

• Given a rooted tree T, and a list L of functions corresponding to the nodes of T, is there a canonical way to write a function F of the arguments T and L that returns the composition of the functions in L structured according to the tree T?

In this way, the "wiring" of the composition—the tree T—is separated from its internal "components"—the list L. A "canonical" solution should include, in particular, representations of T and L that are naturally adapted to this problem.

I suspect that this problem has a trivial solution in a functional programming language, but ideally I would like to have a solution in a dynamically-typed imperative language like Python, something like

def treecomp(tree, list_of_funcs):
    ...
    return function

F = treecomp(T, L)

Addendum

In the meantime, I came up with my own solution (posted below).

While I am satisfied with its economy and conceptual simplicity, I would nevertheless be interested in other essentially different approaches, especially those that leverage strengths in another language that are either lacking or poorly supported in Python.

Hunch

With proper data structures—that don't essentially reproduce the desired output!—functional-programming idioms should enable a very short solution.

Answer 1

Right, so this sounds like an interesting thing to me. So I've gave it a try and here's the result.

class Node(object):
    def __init__(self, parents, fn):
        self.parents = parents
        self.fn = fn

    def get_number_of_args(self):
        if not self.parents:
            return 1
        if not hasattr(self, '_cached_no_args'):
            self._cached_no_args = sum(
                parent.get_number_of_args() for parent in self.parents
            )
        return self._cached_no_args

    def compose(self):
        if not self.parents:
            def composition(*args):
                return self.fn(*args)
            return composition

        fns = []
        fns_args = []
        for parent in self.parents:
            fns.append(parent.compose())
            fns_args.append(parent.get_number_of_args())
        number_of_args = sum(fns_args)
        length = len(self.parents)

        def composition(*args):
            if len(args) != number_of_args:
                raise TypeError
            sub_args = []
            last_no_args = 0
            reached_no_args = 0
            for i in range(length):
                fn = fns[i]
                no_args = fns_args[i]
                reached_no_args += no_args
                args_cut = args[last_no_args: reached_no_args]
                sub_call = fn(*args_cut)
                sub_args.append(sub_call)
                last_no_args = no_args
            return self.fn(*sub_args)

        return composition

You didn't specify the way you implement the tree structure so I combined both nodes and functions into one structure (you can always do mapping yourself). Now the usage:

>>> def fn(x):
...     return x
>>> def fn2(x):
...    return 1
>>> def add(x, y):
...    return x + y
>>> n1 = Node([], fn)
>>> n2 = Node([], fn2)
>>> n3 = Node([n1, n2], add)
>>> fn = n3.compose()
>>> print(fn(5, 7))
6

as expected. Feel free to test it (I actually haven't tried it on deeper tree) and let me know if you find any issues.

Answer 2

We define a function treecomp that returns the composition of a list of functions L structured according to a rooted tree T, by taking L and T as separate arguments:

F = treecomp(T, L)

Unlike the other solutions proposed thus far, it isn't complicated by unnecessary bookkeeping, such as tracking the number of leaves or arguments (which is better handled by decorators, besides).

A simple construction of treecomp

A straightforward realization of treecomp is the following: it merely generates a symbolic (string) expression of the tree composition. Evaluation on arguments is then just a matter of plugging them in and evaluating the resulting expression.

This naive idea can be implemented using fairly basic data structures: lists for the tree and functions, and a simple class for the function-labeled tree. (Namedtuples would also do. However, by using a class with special comparison methods, we can write more semantically natural code.)

Data structures

The most economical encoding of a rooted tree as a flat list is as a list of "node addresses." In a comment to @JeD, I hinted that this could be done by "drawing" the tree:

T = [(0,),
         (0, 0),
             (0, 0, 0),
                 (0, 0, 0, 0), (0, 0, 0, 1), (0, 0, 0, 2),
         (0, 1),
             (0, 1, 0),
                 (0, 1, 0, 0),
             (0, 1, 1),
                 (0, 1, 1, 0), (0, 1, 1, 1)]

Here (0,) is the node corresponding to a0, (0, 0) is the node corresponding to b0, (0, 1) is the node corresponding to b1, and so forth, like the numbering of sections in a book. The longest (or "highest") tuples are the leaves.

The list of functions L can then be given as a list matching the order of nodes in T:

L = [a0, b0, c0, e0, e1, e2, b1, d0, f0, d1, g0, g1]

Since the nodes of the tree T are labeled by the functions in L, it will be convenient to have a data structure for that. We define a class that records a node's address and the literal name of the function labeling it; its methods implement comparisons relative to the partial ordering of the tree (where the root is the minimum element):

class SymbNode:
    '''Class that records a node's address and symbol.'''

    def __init__(self, addr, symb):
        self.addr = addr
        self.symb = symb

    def __len__(self): # how "high" a node is above the root
        return len(self.addr)

    def _compare(self, other, segment):
        return self.addr == other.addr[:segment]

    def __le__(self, other):
        return self._compare(other, segment=len(self))

    def begets(self, other):
        return self._compare(other, segment=-1)

Implementation

The simple two-step mechanism of treecomp is implemented below. By normalizing the order of the list of SymbNodes, we can build up a symbolic expression by simply "peeling off" each layer of the tree as we move up it.

from functools import partial
from operator import attrgetter

def treecomp(tree, funcs):
    '''Returns the composition of a tree of functions.'''
    symbtree = makesymbtree(tree, funcs)
    symbexp = makesymbexp(symbtree)
    return partial(evalsymbexp, symbexp=symbexp)

FUNC_CALL = '{func}({{}})'

def makesymbtree(tree, funcs):
    '''Returns the symbolic expression of a tree composition.'''
    symbols = [FUNC_CALL.format(func=func.__name__) for func in funcs]
    symbtree = sorted((SymbNode(*x) for x in zip(tree, symbols)),
                      key=attrgetter('addr'))
    symbtree.sort(key=len)
    return symbtree

def makesymbexp(symbtree):
    root = symbtree[0]
    if len(symbtree) == 1: # symbtree is a leaf node
        return root.symb
    symbargs = [makesymbexp(subsymbtree(symbtree, root=node))
                for node in symbtree if root.begets(node)]
    return root.symb.format(','.join(symbargs))

def subsymbtree(symbtree, root):
    subsymbtree = [node for node in symbtree if root <= node]
    return subsymbtree

ARGS = 'args[{idx}]'

def evalsymbexp(symbexp, *args):
    '''Returns the evaluation of a symbolic expression on arguments.'''
    argnames = [ARGS.format(idx=str(n)) for n, _ in enumerate(args)]
    return eval(symbexp.format(*argnames))

Verification

Because of the compartmentalization of treecomp, we only need to verify that the function makesymbexp generates the correct symbolic expression, and that the function evalsymbexp properly evaluates symbolic expressions.

The (essentially one-line) function evalsymbexp is supposed to take a string template and plug in the argument names 'args[0]', 'args[1]', etc., then evaluate the result. It evidently does that.

As for makesymbexp, we can gain confidence in its correctness, in lieu of a formal proof (which we eschew), by checking its output on some test data. Take, for example, the following functions:

def D(x): return 2*x
def M(x): return -x
def S(*xs): return sum(xs)

a0 = S
b0, b1 = D, S
c0, d0, d1 = S, D, S
e0, e1, e2, f0, g0, g1 = D, M, D, M, D, M

With T and L as above, we can check that we get the right symbolic expression:

makesymbexp(makesymbtree(T, L))

indeed yields the string

'S(D(S(D({}),M({}),D({}))),S(D(M({})),S(D({}),M({}))))'

To check the delegation of treecomp to evalsymbexp, as a partial function, I verified that the value of

F = treecomp(T, L)
F(x0, x1, x2, x3, x4, x5)

agreed with the value of

a0(b0(c0(e0(x0), e1(x1), e2(x2))), b1(d0(f0(x3)), d1(g0(x4), g1(x5))))

on 1000 random samples of x0, … , x5 drawn from the integers between -100 and 100.