6
\$\begingroup\$

To learn tree traversal i implemented os.walk, tail-recursive and stack-based. Unfortunately Python doesn't support tail call optimization. How do i rewrite my function so that it is maximally functional paradigm compliant? I want to keep side-effects to minimum yet not dive into deep recursions.

def walk_rec(path):
    def i(result, stack):
        if not stack:
            return result
        else:
            path = stack.pop()
            with cd(path):
                ds, fs = partition(isdir, listdir(path))
            stack.extend(join(path, d) for d in ds)
            result.append((path, ds, fs))
            return i(result, stack)
    return i([], [expanduser(path)])

def walk_iter(path):
    stack = [expanduser(path)]
    result = []
    while stack:
        path = stack.pop()
        with cd(path):
            ds, fs = partition(isdir, listdir(path))
        stack.extend(join(path, d) for d in ds)
        result.append((path, ds, fs))
    return result

See: cd, partition.

I could get rid of cd, but this is not critical.

with cd(path):
    ds, fs = partition(isdir, listdir(path))
# can be replaced with
ds, fs = partition(lambda d: isdir(join(path, d)),
                   listdir(path))
\$\endgroup\$
1
\$\begingroup\$

Does this help? In your walk_iter, instead of using pop, grab the first element of the stack. Then do something like this ...

if first_element_has_sub_elements:
    new_stack = stack[0][1]
    new_stack.extend(stack[1:])
    stack = new_stack[:]
else:
    stack = stack[1:]

This was my experiment, in case it's helpful ...

TREE = [
 ("L1A", [("L1A2A",), 
          ("L1A2B", [("L1A2B3A", )])]),
 ("L1B", [("L1B2A", [("L1B2A3A", )])]),
 ("L1C",),
 ("L1D", [("L1D2A",), 
          ("L1D2B", [("L1D2B3A", ),
                     ("L1D2B3B",)])]),
 ]

EXPECTED = ["L1A", "L1A2A", "L1A2B", "L1A2B3A",
            "L1B", "L1B2A", "L1B2A3A", "L1C", 
            "L1D", "L1D2A", "L1D2B", "L1D2B3A", "L1D2B3B"]

def traverse_tree(TREE):
    chopped_tree = TREE[:]
    results = []
    while chopped_tree:
        results.append(chopped_tree[0][0])
        if len(chopped_tree[0]) > 1:
            new_tree = chopped_tree[0][1]
            new_tree.extend(chopped_tree[1:])
            chopped_tree = new_tree[:]
        else:
            chopped_tree = chopped_tree[1:]

    return results

if __name__ == "__main__":
    results = traverse_tree(TREE)
    if results == EXPECTED:
        print "OK"
    else:
        print "MISMATCH"
    print "Expected: "
    print EXPECTED
    print "Results: "
    print results
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.