def identity(x):
return x
def foldsh(tree, branch= lambda tree,ch: list(ch), leaf=identity, shared=identity, getchildren=iter):
'''Sharing-aware tree transformations.
foldsh(tree,branch,leaf,shared,getchildren) :: tree -> result
branch :: tree, list of children's results -> result
leaf :: tree -> result
shared :: result -> result
getchildren :: tree -> iterable of children'''
mem = dict()
def _fold(tree):
if id(tree) in mem:
return shared(mem[id(tree)])
else:
try:
children = getchildren(tree)
except:
res = leaf(tree)
else:
reschildren = [_fold(child) for child in children]
res = branch(tree,reschildren)
mem[id(tree)] = res
return res
return _fold(tree)
Diff to Previous Revision
--- revision 1 2012-05-04 09:04:29
+++ revision 2 2012-05-07 08:20:58
@@ -20,10 +20,9 @@
children = getchildren(tree)
except:
res = leaf(tree)
- mem[id(tree)] = res
- return res
- reschildren = [_fold(child) for child in children]
- res = branch(tree,reschildren)
+ else:
+ reschildren = [_fold(child) for child in children]
+ res = branch(tree,reschildren)
mem[id(tree)] = res
return res
return _fold(tree)