Top-rated recipes tagged "sharing"http://code.activestate.com/recipes/tags/sharing/top/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:
>>> subtree = [42,44]
>>> tree = [subtree,[subtree]]
# We can apply a function to all leaves:
>>> foldsh(tree, leaf= lambda x: x+1)
[[43, 45], [[43, 45]]]
# Or apply a function to the branches:
>>> foldsh(tree, branch= lambda t,c: list(reversed(c)))
[[[44, 42]], [44, 42]]
# The sharing is preserved:
>>> _[0][0] is _[1]
True
# Summing up the leaves without double counting of shared subtrees:
>>> 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>