Trees
Rustom Mody
rustompmody at gmail.com
Tue Jan 20 13:15:58 EST 2015
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])
More information about the Python-list
mailing list