Welcome, guest | Sign In | My Account | Store | Cart
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)

History