title: Composition of a hierarchy of functions
body: <p>Is there a canonical way to express a function that is a composition of a rooted tree of functions?</p>
  
  <p>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:</p>
  
  <p><a href="https://i.stack.imgur.com/zTEAB.jpg" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/zTEAB.jpg" alt="enter image description here"></a></p>
  
  <p>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</p>
  
  <pre><code>F = a0(b0(c0(e0, e1, e2)), b1(d0(f0), d1(g0, g1)))
  </code></pre>
  
  <p>More explicitly, <code>F</code> is a function of 6 arguments that are evaluated by the functions at the leaves:</p>
  
  <pre><code>F(x0, ... , x5) == a0(b0(c0(e0(x0), e1(x1), e2(x2))),
                        b1(d0(f0(x3)), d1(g0(x4), g1(x5))))
  </code></pre>
  
  <p><strong>General question</strong></p>
  
  <ul>
  <li>Given a rooted tree <code>T</code>, and a list <code>L</code> of functions corresponding to the nodes of <code>T</code>, is there a <em>canonical</em> way to write a function <code>F</code> of the arguments <code>T</code> and <code>L</code> that returns the composition of the functions in <code>L</code> structured according to the tree <code>T</code>?</li>
  </ul>
  
  <p>In this way, the "wiring" of the composition—the tree <code>T</code>—is separated from its internal "components"—the list <code>L</code>. A "canonical" solution should include, in particular, representations of <code>T</code> and <code>L</code> that are naturally adapted to this problem.</p>
  
  <p>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 <strong>Python</strong>, something like</p>
  
  <pre><code>def treecomp(tree, list_of_funcs):
      ...
      return function
  
  F = treecomp(T, L)
  </code></pre>
  
  <h2>Addendum</h2>
  
  <p>In the meantime, I came up with my own solution (posted below).</p>
  
  <p>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.</p>
  
  <h3>Hunch</h3>
  
  <p>With proper data structures—that don't essentially reproduce the desired output!—functional-programming idioms should enable a very short solution.</p>