In Lisp, should lists be replaced with trees?

A list structure is already a 'dictionary tree', except it has lousy performance in access. (only really visible on large data sets).<p>* (second (assoc 5 '((1 2) (3 4) (5 6))))<p>&#62; 6<p>The lousy performance doesn't matter, most of the time, because you have other data-structures for data, and your compiler generally is only interested in sequential access (constructing a parse tree out of it). The lisp code already being a tree makes parsing fairly simple...<p>So, I guess my point is that I don't see the point of this?<p>The only reason to really upgrade to a dictionary would be if you wanted to have non-sequential access to the contents of of your large-scale code-data-structure... generally the lists aren't large enough to merit it. You can do all of the dictionary operations on a list, and they are 'fast enough'. ----<p>I feel like the rationale here is created by conflating the idea of a cons and a list. I think generally, a list already accomplishes what the author sets out to accomplish.<p>They are a single step higher level than conses, and give you a hierarchical structure with the possibility for named associations. I don't really see how using something more complicated and memory intensive to build this basic data structure qualifies as an improvement...

not 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.<p>[1] <a href="http://labs.oracle.com/projects/plrg/Publications/ICFPAugust2009Steele.pdf" rel="nofollow">http://labs.oracle.com/projects/plrg/Publications/ICFPAugust...</a>

A 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: <a href="http://vimeo.com/6624203" rel="nofollow">http://vimeo.com/6624203</a>

"Branchs/trees are a superset of pairs/lists"<p>No, they aren't. A tree is acyclic by definition. Cons cells allow circular structures.

Will Thimbleby (<a href="http://will.thimbleby.net/misc-an-experimental-language/" rel="nofollow">http://will.thimbleby.net/misc-an-experimental-language/</a>) also explored similar ideas.

It's easy to implement both lists and name-value associations in terms of pairs, so I'm not sure why they need to be built in.<p>In Fexl (<a href="http://fexl.com/code" rel="nofollow">http://fexl.com/code</a>), the only built in concept is the <i>function</i>, and all data is structured out of functions. I won't go into all the details here, but concepts like pair, list, key-value assoc, branch, and everything else are readily expressed as pure functions. So-called "circular" structures are created with the Y combinator, so they really are not circular in memory, only in concept.

Lisp is already made of trees. A Lisp program is a pre-order traversal of the abstract syntax tree of a yacc'ed program in another programming language. This fact is WHY Lisp is powerful. By eliminating yaccing you can create new syntax on the fly without having to recompile your compiler.

By "replacing" lists with trees, am I supposed to understand that working with trees will be natural and easy, and lists will feel like second-class citizens? I thought we were beyond thinking like that. Building languages around a favorite data structure was never the right thing to do; it was always tunnel vision and bad design. Different data structures have different features and different performance characteristics. There's no reason for a language designer to pick a favorite data structure and force anyone who has to use a different one to deal with warts and second-class library and language support.

He seems to have heard of Lua but that didn't stop him from raising the question.<p>Next article: "<i>Should airplanes be fitted with big rotor on top to allow for vertical take off and hovering? .. like helicopters?</i>"

I wouldn't say lists should be <i>replaced</i> with trees, but adding a rich set of tree-based data structures to Lisp improves it substantially, in my view. To see what I mean, have a look at my FSet functional collections package, which does exactly that:<p><pre><code> http://common-lisp.net/project/fset/ </code></pre> Unlike what the OP is suggesting, FSet doesn't expose the internal structure of its trees. Instead it wraps them in a rich set-theoretic interface.

You can just build your tree data structure and develop operators to work with them in Lisp. There's nothing that restricts you to using lists.<p>So what's the point of "replacing" them (even if such a thing were possible without "replacing" Lisp)?

A few people have asked, what is the point? since trees and associative access can just be implemented with lists.<p>It is the same basic point as having 'let' or 'case' etc. (which can all just be implemented with 'lambda' and 'if' etc.) -- it is just a bit higher-level to program with.<p>With something that makes programming a little easier (maybe), probably the question ought really be, why <i>shouldn't</i> we have it?

This is either a reinvention of ASTs or it's Graph Reduction.<p><a href="http://en.wikipedia.org/wiki/Abstract_syntax_tree" rel="nofollow">http://en.wikipedia.org/wiki/Abstract_syntax_tree</a> <a href="http://en.wikipedia.org/wiki/Graph_reduction" rel="nofollow">http://en.wikipedia.org/wiki/Graph_reduction</a><p>:)

Lists are trees.

Wouldn't that make it a new language called Trep?