http://code.activestate.com/recipes/tags/fold-tree/2012-06-20T08:09:13-07:00ActiveState Code Recipes2012-06-20T08:09:13-07:00Sander Evershttp://code.activestate.com/recipes/users/4173111/http://code.activestate.com/recipes/578118-cycle-aware-tree-transformations/

<p style="color: grey"> Python recipe 578118 by <a href="/recipes/users/4173111/">Sander Evers</a> (<a href="/recipes/tags/cyclic/">cyclic</a>, <a href="/recipes/tags/fold/">fold</a>, <a href="/recipes/tags/reduce/">reduce</a>, <a href="/recipes/tags/yaml/">yaml</a>). </p> <p>A variation on <a href="http://code.activestate.com/recipes/578117/">Recipe 578117</a> that can deal with cycles. A cycle means that a tree has itself as a subtree somewhere. A fold over such a data structure has a chicken-and-egg-problem: it needs its own result in order to construct its own result. To solve this problem, we let <code>branch</code> construct a <em>part</em> of its result before going into recursion. After the recursion, <code>branch</code> gets a chance to complete its result using its children's results. Python's support for coroutines (using <code>yield</code>) provides a nice way to define such a two-stage <code>branch</code> function.</p>