Composition of a hierarchy of functions

Viewed 6343

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:

enter image description here

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.

5 Answers
Related