Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #84060 > unrolled thread

Re: Trees

Back to article view | Back to comp.lang.python

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: Trees Terry Reedy <tjreedy@udel.edu> - 2015-01-20 01:08 -0500
    Re: Trees Marko Rauhamaa <marko@pacujo.net> - 2015-01-20 11:45 +0200
      Re: Trees Paul Rubin <no.email@nospam.invalid> - 2015-01-20 10:14 -0800
        Re: Trees Marko Rauhamaa <marko@pacujo.net> - 2015-01-20 22:26 +0200
      Re: Trees Stephen Hansen <me+python@ixokai.io> - 2015-01-20 23:56 -0800
        Re: Trees Marko Rauhamaa <marko@pacujo.net> - 2015-01-21 10:35 +0200
        Re: Trees Rustom Mody <rustompmody@gmail.com> - 2015-01-21 04:09 -0800
          Re: Trees Chris Angelico <rosuav@gmail.com> - 2015-01-21 23:35 +1100
            Re: Trees Rustom Mody <rustompmody@gmail.com> - 2015-01-21 07:24 -0800
          Re: Trees Tim Chase <python.list@tim.thechases.com> - 2015-01-21 06:55 -0600
          Re: Trees Chris Angelico <rosuav@gmail.com> - 2015-01-22 00:01 +1100
          Re: Trees Tim Chase <python.list@tim.thechases.com> - 2015-01-21 08:26 -0600
          Re: Trees Chris Angelico <rosuav@gmail.com> - 2015-01-22 01:31 +1100
          Re: Trees Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-01-22 01:47 +1100
            Re: Trees Ian Kelly <ian.g.kelly@gmail.com> - 2015-01-21 09:15 -0700
            Re: Trees Ian Kelly <ian.g.kelly@gmail.com> - 2015-01-21 10:27 -0700
    Re: Trees Rustom Mody <rustompmody@gmail.com> - 2015-01-20 05:33 -0800
      Re: Trees Rustom Mody <rustompmody@gmail.com> - 2015-01-20 05:51 -0800
      Re: Trees Marko Rauhamaa <marko@pacujo.net> - 2015-01-20 16:15 +0200
        Re: Trees Rustom Mody <rustompmody@gmail.com> - 2015-01-20 06:35 -0800
      Re: Trees Ian Kelly <ian.g.kelly@gmail.com> - 2015-01-20 10:19 -0700
        Re: Trees Rustom Mody <rustompmody@gmail.com> - 2015-01-20 10:15 -0800
          Re: Trees Rustom Mody <rustompmody@gmail.com> - 2015-01-20 10:35 -0800
      Re: Trees Mario <marfig@gmail.com> - 2015-01-20 22:47 +0100
        Re: Trees Rustom Mody <rustompmody@gmail.com> - 2015-01-20 17:23 -0800
          Re: Trees Paul Rubin <no.email@nospam.invalid> - 2015-01-20 17:49 -0800
            Re: Trees Rustom Mody <rustompmody@gmail.com> - 2015-01-20 18:03 -0800
              Re: Trees Paul Rubin <no.email@nospam.invalid> - 2015-01-21 14:27 -0800
                Re: Trees Rustom Mody <rustompmody@gmail.com> - 2015-01-21 21:17 -0800
          Re: Trees Ian Kelly <ian.g.kelly@gmail.com> - 2015-01-21 15:54 -0700
            Re: Trees Rustom Mody <rustompmody@gmail.com> - 2015-01-21 21:20 -0800
              Re: Trees Ian Kelly <ian.g.kelly@gmail.com> - 2015-01-22 00:01 -0700
              Re: Trees Ian Kelly <ian.g.kelly@gmail.com> - 2015-01-21 23:56 -0700
            Re: Trees Paul Rubin <no.email@nospam.invalid> - 2015-01-21 23:16 -0800
              Re: Trees Rustom Mody <rustompmody@gmail.com> - 2015-01-22 08:54 -0800
        Re: Trees Terry Reedy <tjreedy@udel.edu> - 2015-01-20 21:19 -0500
          Re: Trees Mario Figueiredo <marfig@gmail.com> - 2015-01-21 14:05 +0000

Page 2 of 2 — ← Prev page 1 [2]

#84074

On Tue, Jan 20, 2015 at 6:33 AM, Rustom Mody <rustompmody@gmail.com> 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.

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

def dfs(t):
    yield t[0]
    yield from chain.from_iterable(map(dfs, islice(t, 1, None)))

> # Converting to generators is trivial
> =====================

:-)

[toc] | [prev] | [next] | [standalone]

#84081

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

[toc] | [prev] | [next] | [standalone]

#84083

On Tuesday, January 20, 2015 at 11:46:11 PM UTC+5:30, Rustom Mody wrote:
> 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:
> > > # 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])

Ok got it
Forgot the
«yield t[1]»
before the two yield-from's

[toc] | [prev] | [next] | [standalone]

#84092

In article <d34dbfbe-fe82-47dc-8bc3-c8773e2b70dd@googlegroups.com>, 
rustompmody@gmail.com says...
> 
> Yeah python has trees alright.
> 
> Heres' some simple tree-code

Didn't you just demonstrate that Python has no trees and instead you 
have to implement them yourself (or use a third-party implementation)?

I don't know what's the point of all this vain and misleading play with 
words. Not only most languages don't implement trees in their standard 
libraries (its no shame, it's no sin), but also it's quite evident that 
there's a big difference between implementing a data structure yourself 
through the application of language facilities and seeing that data 
structure already implemented for you in the standard library.

[toc] | [prev] | [next] | [standalone]

#84097

On Wednesday, January 21, 2015 at 3:18:03 AM UTC+5:30, Mario wrote:
> rustompmody says...
> > 
> > Yeah python has trees alright.
> > 
> > Heres' some simple tree-code
> 
> Didn't you just demonstrate that Python has no trees and instead you 
> have to implement them yourself (or use a third-party implementation)?
> 
> I don't know what's the point of all this vain and misleading play with 
> words. 

Point.

You snipped off Terry's lines which I was replying (rather adding) to:

> Sequences nested withing sequences can be regarded as trees, and Python
> has these.  I regard Lisp as a tree processing languages, as it must be
> to manipulate, for example, code with nested structures. 

To those who are familiar with Lisp this is not new.
To others it is likely too dense to be easily comprehensible.

> Not only most languages don't implement trees in their standard 
> libraries (its no shame, it's no sin), but also it's quite evident that 
> there's a big difference between implementing a data structure yourself 
> through the application of language facilities and seeing that data 
> structure already implemented for you in the standard library.

Its not a binary but a spectrum.

Do the equivalent of "implement yourself with language facilities"
in C or Java for the above code and you will see one end of the spectrum.

Here's Haskell at the other end of the spectrum:
[Renamed the (I)nternal tag to the (B)ranch tag because of I-1 visual clash]

===================

## The type

data Tree t = L t | B t (Tree t) (Tree t)

## The depth first algorithm

dfs (L x)   = [x]
dfs (B x lst rst) = [x]  ++  dfs lst  ++  dfs rst

## Example tree:

t = (B 6 (B 2 (L 1) (B 4 (L 3) (L 5))) (B 8 (L 7) (L 9)))

## Example run

*Main> dfs t
[6,2,1,4,3,5,8,7,9]

==================
The Haskell is bullseye¹ in capturing the essense of a tree because
conceptually a tree of type t is recursive in the sense that it can contain
2 subtrees -- (B x lst rst) -- or its a base case -- L x.

The same thing in C needs a mutually recursive data structure:

One needs two types – a node *containing*  pointers; a pointer *pointing* to node

And then go from binary to n-ary trees and the shit hits the ceiling:
4-way mutual recursion: Tree-node, tree-node-pointer; list-node; list-pointer.

Completely transparent in Haskell:

data Nary t = Tr t [Nary t]

Python's not as trivial to get right as Haskell
[get one of the subtrees wrong and the error-messages are quite unhelpful]
However its way better than C.

So there's a spectrum C → Java → Python → Haskell → Tree-DSL²

============
¹ Well not quite bullseye because a mathematician would prefer a
*set* of subtrees where we get at best a *list*

² eg UUAG http://www.andres-loeh.de/AGee.pdf

[toc] | [prev] | [next] | [standalone]

#84098

Rustom Mody <rustompmody@gmail.com> writes:
> ## The depth first algorithm
> dfs (L x)   = [x]
> dfs (B x lst rst) = [x]  ++  dfs lst  ++  dfs rst

Cute.  I can't resist posting the similar breadth first algorithm:

bfs (L x)   = [x]
bfs (B x lst rst) = bfs lst  ++ [x] ++  bfs rst

> *Main> dfs t
> [6,2,1,4,3,5,8,7,9]

*Main> bfs t
[1,2,3,4,5,6,7,8,9]

> The Haskell is bullseye¹ in capturing the essense of a tree because
> conceptually a tree of type t is recursive in the sense that it can contain
> 2 subtrees -- (B x lst rst) -- or its a base case -- L x.

You might like this discussion of a red-black tree implementation whose
datatype makes sure the RB tree invariants are preserved.  The data
definition is kind of verbose, but with more recent GHC versions it can
be made a lot crisper, with datakinds and type-level numeric literals.

https://www.reddit.com/r/haskell/comments/ti5il/redblack_trees_in_haskell_using_gadts_existential/

[toc] | [prev] | [next] | [standalone]

#84099

On Wednesday, January 21, 2015 at 7:19:39 AM UTC+5:30, Paul Rubin wrote:
> Rustom Mody  writes:
> > ## The depth first algorithm
> > dfs (L x)   = [x]
> > dfs (B x lst rst) = [x]  ++  dfs lst  ++  dfs rst
> 
> Cute.  I can't resist posting the similar breadth first algorithm:
> 
> bfs (L x)   = [x]
> bfs (B x lst rst) = bfs lst  ++ [x] ++  bfs rst
> 
> > *Main> dfs t
> > [6,2,1,4,3,5,8,7,9]
> 
> *Main> bfs t
> [1,2,3,4,5,6,7,8,9]

Eh??

Thats not bfs. That's inorder traversal

The bfs of http://www-math.ucdenver.edu/~wcherowi/courses/m4408/gtln8.html

is
[6,    2,8,      1,4,7,9,      3,5]

[toc] | [prev] | [next] | [standalone]

#84148

Rustom Mody <rustompmody@gmail.com> writes:
> Thats not bfs. That's inorder traversal

Oops, you're right.  How's this:

bfs x = go [x] where
  go [] = []
  go (L x:ts) = x:go ts
  go (B x lst rst:ts) = x : go (ts ++ [lst, rst])

*Main> bfs t
[6,2,8,1,4,7,9,3,5]

[toc] | [prev] | [next] | [standalone]

#84188

On Thursday, January 22, 2015 at 3:57:50 AM UTC+5:30, Paul Rubin wrote:
> Rustom Mody  writes:
> > Thats not bfs. That's inorder traversal
> 
> Oops, you're right.  How's this:
> 
> bfs x = go [x] where
>   go [] = []
>   go (L x:ts) = x:go ts
>   go (B x lst rst:ts) = x : go (ts ++ [lst, rst])
> 
> *Main> bfs t
> [6,2,8,1,4,7,9,3,5]

Yeah thats right.
And now you can get the duality between dfs and bfs you were earlier after by
replacing the 
ts ++ [lst,rst]
with
[lst,rst] ++ ts

BTW this is just converting queue to stack;
And its neat; and out of reach of those who think only imperatively

PS
1. Ive not tried it
2. For n-ary trees its neater
3. In my imaginary language with first-class sets, bags, lists it would be neater still

[toc] | [prev] | [next] | [standalone]

#84151

On Tue, Jan 20, 2015 at 6:23 PM, Rustom Mody <rustompmody@gmail.com> wrote:
> The Haskell is bullseye¹ in capturing the essense of a tree because
> conceptually a tree of type t is recursive in the sense that it can contain
> 2 subtrees -- (B x lst rst) -- or its a base case -- L x.

How do you create a tree containing an even number of elements under
this constraint?

[toc] | [prev] | [next] | [standalone]

#84189

On Thursday, January 22, 2015 at 4:25:03 AM UTC+5:30, Ian wrote:
> On Tue, Jan 20, 2015 at 6:23 PM, Rustom Mody wrote:
> > The Haskell is bullseye¹ in capturing the essense of a tree because
> > conceptually a tree of type t is recursive in the sense that it can contain
> > 2 subtrees -- (B x lst rst) -- or its a base case -- L x.
> 
> How do you create a tree containing an even number of elements under
> this constraint?

Not sure what you are asking...

[And a text only group makes discussing pictur-esque things hard]
What do you mean by 'element'?
Leaf? Internal? Either?

[toc] | [prev] | [next] | [standalone]

#84201

On Wed, Jan 21, 2015 at 11:56 PM, Ian Kelly <ian.g.kelly@gmail.com> wrote:
> Since each element is associated with a node, the question could
> equally be phrased as "How do you create a tree containing an even
> number of elements under this constraint?"

Of course I meant to write "nodes" there, not "elements".

[toc] | [prev] | [next] | [standalone]

#84202

On Wed, Jan 21, 2015 at 10:20 PM, Rustom Mody <rustompmody@gmail.com> wrote:
> On Thursday, January 22, 2015 at 4:25:03 AM UTC+5:30, Ian wrote:
>> On Tue, Jan 20, 2015 at 6:23 PM, Rustom Mody wrote:
>> > The Haskell is bullseye¹ in capturing the essense of a tree because
>> > conceptually a tree of type t is recursive in the sense that it can contain
>> > 2 subtrees -- (B x lst rst) -- or its a base case -- L x.
>>
>> How do you create a tree containing an even number of elements under
>> this constraint?
>
> Not sure what you are asking...
>
> [And a text only group makes discussing pictur-esque things hard]
> What do you mean by 'element'?
> Leaf? Internal? Either?

By "element" I mean an individual datum contained in the tree.
Likewise the elements of a list are its contents.

Since each element is associated with a node, the question could
equally be phrased as "How do you create a tree containing an even
number of elements under this constraint?" The point I was driving at
is that the definition is incomplete -- in addition to being an
internal node or a leaf, a tree can also be empty. In fact I would
suggest that an empty tree should be the real base case, since what is
a leaf node but a node where both of its children are empty trees?

[toc] | [prev] | [next] | [standalone]

#84203

Ian Kelly <ian.g.kelly@gmail.com> writes:
> How do you create a tree containing an even number of elements under
> this constraint?

That's a good point, I've usually seen different definitions of trees,
e.g.

   data Tree a = Leaf | Branch a (Tree a) (Tree a)

so a Leaf node doesn't have a value associated with it.

  https://en.wikipedia.org/wiki/File:Red-black_tree_example.svg

has a picture of such a tree--don't worry about the node coloring for
this purpose.  Or the multi-way tree with arbitrary branching width:

   data RoseTree a = RoseTree a [RoseTree a]

Each node has a value and a list of zero or more subtrees.

[toc] | [prev] | [next] | [standalone]

#84239

On Thursday, January 22, 2015 at 12:46:22 PM UTC+5:30, Paul Rubin wrote:
> Ian Kelly writes:
> > How do you create a tree containing an even number of elements under
> > this constraint?
> 
> That's a good point, I've usually seen different definitions of trees,
> e.g.
> 
>    data Tree a = Leaf | Branch a (Tree a) (Tree a)
> 
> so a Leaf node doesn't have a value associated with it.

Maybe you should call 'Leaf' instead as EmptyTree 

Then does it answer Ian's question?

Or Nil Null or some such then it is most obviously isomorphic to
the typical way of doing it in C.

The point is that these are frameworks for structural induction.
So choosing base-cases carefully is important.

This may seem harmless but is probably not a good idea

  data Tree a = Empty | Leaf a | Branch a (Tree a) (Tree a)

OTOH the classic S-exp of lisp would be modelled as

 data Sexp b = Cons (Sexp b) (Sexp b) | Leaf b

which captures the fact that the elements (b) are only at the leaves
and the conses provide pure branching without content

ie its not ... Cons b (Sexp b) (Sexp b)...

[toc] | [prev] | [next] | [standalone]

#84100

On 1/20/2015 4:47 PM, Mario wrote:
> In article <d34dbfbe-fe82-47dc-8bc3-c8773e2b70dd@googlegroups.com>,
> rustompmody@gmail.com says...
>>
>> Yeah python has trees alright.
>>
>> Heres' some simple tree-code
>
> Didn't you just demonstrate that Python has no trees and instead you
> have to implement them yourself (or use a third-party implementation)?
>
> I don't know what's the point of all this vain and misleading play with
> words.

It is not play with words. A tree is a recursive - nested - hierachical 
data structure with the restriction of no cycles or alternate pathways. 
  Python collections whose members are general objects, including 
collections, can be nested.  The resulting structures *are* tree 
structures, if not more general directed graphs.  They are quite 
commonly used in Python.

The common question -- "How do I flatten a list" -- is asking "How to I 
turn a list from a tree (or DAG, but not a cyclic graph*) into a 
sequence of leaf objects".  The question illustrates what is missing - 
builtin functions or methods for nested collections.  I already 
suggested that there *might* be a useful addition in this direction.

* A Python interpreter needs to take special measures to even display an 
infinitely recursive list without raising or even segfaulting.  Most 
posted 'flatten' functions do not account for this possibility.

 >>> l = [1]
 >>> l.append(l)
 >>> l
[1, [...]]


 > Not only most languages don't implement trees in their standard
> libraries

Typically, built-in collection type C has members of type M that does 
not include type C.  Therefore a C instance cannot (directly) contain a 
C instance.  The result is that people write a 'design pattern' to 
overcome the limitation and enable a C to indirectly include a C.  Since 
this limitations does not exist in Python's generalized collections of 
objects, the pattern is unneeded in Python.

-- 
Terry Jan Reedy

[toc] | [prev] | [next] | [standalone]

#84117

Hello Terry,

> It is not play with words. A tree is a recursive - nested -
> hierachical
> data structure with the restriction of no cycles or alternate
> pathways.
> Python collections whose members are general objects, including
> collections, can be nested.  The resulting structures *are* tree
> structures, if not more general directed graphs.  They are quite
> commonly used in Python.

Let's get somethig clear. Tree data structures have an associated logic that 
justifies their name as a de facto Tree Data Structure. If your low level 
description was how you described a tree to someone new to the concept, they 
would be none the wiser about what a Tree represents or what uses they could 
have for them. This logic is no different from the internal logic that diferentiates 
a dictionary from a list and helps carry their distinct operations. Despite 
a dictionary being nothing more than a glorified list.

Just as well, tree data structures only make sense along with their logic. 
Storage, traversal, insertion, random searches, retrieval, etc, all these 
algorithms are what in the end define a Tree data structure and what will 
help categorize it. Python standard library doesn't have any tree data structure 
implementation. It has lists, dictionaries, and other base structures that 
in the end will help define storage patterns for tree data structures. And 
that's it.

A simple binary tree needs to be implemented in Python as a binary tree, 
if it wants to be recognized as such. All your code examples illustrate exactly 
that. And if you care about code reuse, you will want to define a number 
of associated algorithms to take advantage of your storage model and answer 
your performance or memory requirements. Along with your list pattern for 
storage, you will probably also want to implement an insertion/search/update/traversal 
algorithms. That's when you have a tree.

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

Back to top | Article view | comp.lang.python

csiph-web