News for hackers. Stuff that matters.
Re:In Lisp, should lists be replaced with trees? by Turing_Machine on Monday May 16, 2011 @07:48AM (#2552249)
"Branchs/trees are a superset of pairs/lists"

No, they aren't. A tree is acyclic by definition. Cons cells allow circular structures.

Re:In Lisp, should lists be replaced with trees? by Turing_Machine on Monday May 16, 2011 @08:01AM (#2552273)
To take a familiar example, the Web is not a tree. While you might argue that each page has unique children (outlinks), there is no unique parent -- a page can have an arbitrarily large number of incoming links, and the page can link back to those pages in turn, producing cyclic structures of immense complexity.

For some interesting discussion on the limits of tree structures with respect to urban planning see A City is Not a Tree by Christopher Alexander (who is also the inspiration for the Design Patterns movement in software engineering). http://www.rudi.net/node/317

Re:In Lisp, should lists be replaced with trees? by Deestan on Monday May 16, 2011 @08:55AM (#2552372)
All good, just a nitpick: You don't need a unique parent to have a tree. You don't even need directed edges. :)

The purest definition of a tree graph is "a graph with no cycles".

Re:In Lisp, should lists be replaced with trees? by sesqu on Monday May 16, 2011 @02:38PM (#2553632)
We use different definitions. My trees are acyclic connected graphs with one root.
Re:In Lisp, should lists be replaced with trees? by omaranto on Monday May 16, 2011 @09:07AM (#2552396)
The structures described are called trees in the post, but are actually just sets of named objects, which can be used to describe cyclic structures in the same way conses can.
Re:In Lisp, should lists be replaced with trees? by chalst on Monday May 16, 2011 @08:09AM (#2552290)
And this is useful: you can represent the transitions of a state machine in this way, for instance.
Re:In Lisp, should lists be replaced with trees? by Confusion on Monday May 16, 2011 @01:18PM (#2553306)
The structure he calls a 'tree' allows cycles and is a generalization of a list. Whether he uses the correct word isn't really interesting: it doesn't detract anything from the post.