No, they aren't. A tree is acyclic by definition. Cons cells allow circular structures.
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
The purest definition of a tree graph is "a graph with no cycles".
[1] http://labs.oracle.com/projects/plrg/Publications/ICFPAugust...
In Fexl (http://fexl.com/code), the only built in concept is the function, 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.
What's your rationale vbehind everything being a function?
Even something as lowly as a bit (Boolean value true or false) can be represented as a function. In Fexl, the functions for T and F are expressed as:
\T = (\T\F T)
\F = (\T\F F)
eq x 4 (print "Yes, it's 4") (print "No, it's not 4")
\if = (\x x)
if (eq x 4) (print "Yes, it's 4") (print "No, it's not 4")
\null = ( \null\cons null)
\cons = (\head\tail \null\cons cons head tail)
groceries
(print "You don't need anything at the moment")
\head\tail
print "You need "; print head;
print "and possibly some other things."
\empty = (\list list T \_\_ F)
\head = (\list list undef \head\_ head)
\tail = (\list list undef \_\tail tail)
if (empty groceries)
(print "You don't need anything at the moment")
(print "You need "; print (head groceries);
print " and possibly some other things.")
\pair = (\x\y \pair pair x y)
\the_pair = (pair 2.6 3.8)
...
the_pair \x\y
print "left is "; print x;
print "right is "; print y;
If you like, you can download the code at http://fexl.com/code . One of these days I should put a sandboxed demo interpreter up on the site.
Well, in musings around Arc, pg did mention defining everything as a list, including 3 as [[] [] []], I believe. So, it's not that no one says it. :)
* (second (assoc 5 '((1 2) (3 4) (5 6))))
> 6
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...
So, I guess my point is that I don't see the point of this?
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'. ----
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.
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...
Exactly. Much of the time you don't care. The rest of the time, you can still use assoc-lists, except you create a branching structure on the keys such that no key in the list is a prefix of any other. The first entry of a node contains the value "at" that node, and the tail of the node is a list of branches, where each branch is a pair consisting of a string key and a child node.
The "get" and "put" functions in this structure are very simple recursive functions, and you can maintain very large dictionaries ("maps") this way. The get and put operations are essentially O(1), constant time, if you ignore the sheer length of the keys (which are usually reasonably short anyway). I've done tests where I insert hundreds of thousands of pseudo-random keys and values, and read them back, all very quickly and reliably. The code splits the keys into branching structures automatically. It's also a purely functional structure, so you can keep old versions of the maps.
The value at each node can be anything you like, not just a string, though to detect the absence of a value you need to use a "Maybe" type. In Fexl you can define constructors:
\absent = ( \absent\present absent)
\present = (\value \absent\present present value)
You also detect singleton nodes, which have an absent value and only one branch. In that case you can concatenate the key of that branch with the parent key upstairs, eliminating the extra branch.
Next article: "Should airplanes be fitted with big rotor on top to allow for vertical take off and hovering? .. like helicopters?"
So what's the point of "replacing" them (even if such a thing were possible without "replacing" Lisp)?
There also physical/efficiency concerns. There's a reason databases use highly branching trees.
Lisp also has all of the other low-level primitives we're used to when working closer to the machine. Structs, indexed arrays, hashes, etc. If efficiency is a concern, just pick an implementation that compiles to machine code. SBCL is pretty good for this depending on your target platform.
Replacing conses seems like a waste of time.
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.
With something that makes programming a little easier (maybe), probably the question ought really be, why shouldn't we have it?
http://en.wikipedia.org/wiki/Abstract_syntax_tree http://en.wikipedia.org/wiki/Graph_reduction
:)
http://common-lisp.net/project/fset/