On Tuesday, January 20, 2015 at 10:51:13 PM UTC+5:30, Ian wrote: > On Tue, Jan 20, 2015 at 6:33 AM, Rustom Mody wrote: > > from enum import Enum > > class TreeTag(Enum): > > I = 0 # An internal node > > L = 1 # A leaf node > > def __repr__(self): return self.name > > > > I = TreeTag.I > > L = TreeTag.L > > Explicitly tagging nodes as internal or leaves is kind of ugly and > also prone to getting out of sync with the reality, which is that a > node is a leaf if it doesn't have any other nodes hanging off of it.
Yeah... Just demoing a technique for more variegated trees eg an AST for some toy DSL or some such. Imagine you have 10 types of nodes and one defaults to tagless > > > def dfs(t): > > if t[0] == L: > > return [t[1]] > > else: > > return [t[1]] + dfs(t[2]) + dfs(t[3]) > > Over the entire tree, this will do O(n) list additions which implies > O(n) list *copies*, which is rather inefficient. This would probably > be better implemented as a recursive generator. Yeah > > def dfs(t): > yield t[0] > yield from chain.from_iterable(map(dfs, islice(t, 1, None))) > > > # Converting to generators is trivial > > ===================== > > :-) Less trivial than I thought... Why does this not work? def dfsg(t): if t[0] == L: yield t[1] else: yield from dfsg(t[2]) yield from dfsg(t[3]) -- https://mail.python.org/mailman/listinfo/python-list