Trees

[Rustom Mody]

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