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
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))
