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 -- https://mail.python.org/mailman/listinfo/python-list