Popular recipes tagged "sharing"http://code.activestate.com/recipes/tags/sharing/popular/2012-05-07T08:20:58-07:00ActiveState Code RecipesSharing-aware tree transformations (Python) 2012-05-07T08:20:58-07:00Sander Evershttp://code.activestate.com/recipes/users/4173111/http://code.activestate.com/recipes/578117-sharing-aware-tree-transformations/ <p style="color: grey"> Python recipe 578117 by <a href="/recipes/users/4173111/">Sander Evers</a> (<a href="/recipes/tags/fold/">fold</a>, <a href="/recipes/tags/reduce/">reduce</a>, <a href="/recipes/tags/sharing/">sharing</a>, <a href="/recipes/tags/tree/">tree</a>, <a href="/recipes/tags/yaml/">yaml</a>). Revision 2. </p> <p>The function <code>foldsh</code> in this recipe is a general purpose tool for transforming tree-like recursive data structures while keeping track of shared subtrees.</p> <pre class="prettyprint"><code># By default, a branch is encoded as a list of subtrees; each subtree can be a # branch or a leaf (=anything non-iterable). Subtrees can be shared: &gt;&gt;&gt; subtree = [42,44] &gt;&gt;&gt; tree = [subtree,[subtree]] # We can apply a function to all leaves: &gt;&gt;&gt; foldsh(tree, leaf= lambda x: x+1) [[43, 45], [[43, 45]]] # Or apply a function to the branches: &gt;&gt;&gt; foldsh(tree, branch= lambda t,c: list(reversed(c))) [[[44, 42]], [44, 42]] # The sharing is preserved: &gt;&gt;&gt; _[0][0] is _[1] True # Summing up the leaves without double counting of shared subtrees: &gt;&gt;&gt; foldsh(tree, branch= lambda t,c: sum(c), shared= lambda x: 0) 86 </code></pre> <p>In particular, it is useful for transforming YAML documents. An example of this is given below.</p>