In Lisp, should lists be replaced with trees?
1–10 of 43 posts
Re: In Lisp, should lists be replaced with trees?
#2[deleted]
Re: In Lisp, should lists be replaced with trees?
#3not directly lisp related, but the team working on Fortress has some interesting work on using "conc lists" (pairs, and trees as a combination of pairs) as a basic unit of work for parallel processing[1], the analysis quite naturally considers its relation with lisp ad cons lists in other languages.
[1] http://labs.oracle.com/projects/plrg/Publications/ICFPAugust...
Re: In Lisp, should lists be replaced with trees?
#4He seems to have heard of Lua but that didn't stop him from raising the question.
Next article: "Should airplanes be fitted with big rotor on top to allow for vertical take off and hovering? .. like helicopters?"
Re: In Lisp, should lists be replaced with trees?
#5"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?
#6"Branchs/trees are a superset of pairs/lists" No, they aren't. A tree is acyclic by definition. Cons cells allow circular structures.
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?
#7A better reason to replace lists with trees might be for parallel execution. I enjoyed this talk by Guy Steele on replacing lists with trees in Fortress:
http://vimeo.com/6624203
Re: In Lisp, should lists be replaced with trees?
#8not directly lisp related, but the team working on Fortress has some interesting work on using "conc lists" (pairs, and trees as a combination of pairs) as a basic unit of work for parallel processing[1], the analysis quite naturally considers its relation with lisp ad cons lists in other languages. [1] http://labs.oracle.com/projects/plrg/Publications/ICFPAugust...
Also, Guy Steele is one of the two inventor of Scheme. So it may not be directly lisp related, but it definitely is indirectly lisp related ;-).
Re: In Lisp, should lists be replaced with trees?
#9"Branchs/trees are a superset of pairs/lists" No, they aren't. A tree is acyclic by definition. Cons cells allow circular structures.
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?
#10"Branchs/trees are a superset of pairs/lists" No, they aren't. A tree is acyclic by definition. Cons cells allow circular structures.
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…
[deleted]