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 listLof functions corresponding to the nodes ofT, is there a canonical way to write a functionFof the argumentsTandLthat returns the composition of the functions inLstructured according to the treeT?
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.
