Trees

[Rustom Mody]

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