David Brown wrote:
On Thu, Jan 31, 2008 at 03:36:34PM -0800, [EMAIL PROTECTED] wrote:
On Thu, Jan 31, 2008 at 01:35:56PM -0800, Andrew Lentvorski wrote:
DOT indicates a pure pair. It must have exactly one sexpr on the left
and exactly one sexpr on the right.
Don't shoot me but I'm questioning the need for conses and all this "dot"
stuff. Even SICP doesn't mention conses in the first chapter.
Sure it may be a nice optimization but for teaching purposes I don't see
why list can't be *thee* fundamental data structure.
Well, simply, conses _are_ the fundamental data structure. One of the
things you can build out of them are lists, but you can build other things
as well.
Lists are _not_ a primitive type in lisp, like they are in some other
language.
That isn't quite true.
Lists really are a fundamental data structure in lisp. A cons cell is
the basic building block of a singly linked list, and lisp has specific
notations to construct singly linked lists ( (list 1 2 3) builds a
singly linked list as does '(1 2 3) ).
The difference is that many languages (like Python) assign the name
"list" to a data structure that is actually a *vector*.
Vectors have O(1) random access, O(n) insert, O(n) delete, O(1) length,
O(1) empty. These are characteristics of the Python "list".
True lists have O(n) random access, O(1) insert, O(1) delete, O(n)
length, and O(1) empty. Those are *not* characteristics of Python
lists. They *are* characteristics of Lisp lists (aka cons cells).
-a
--
[email protected]
http://www.kernel-panic.org/cgi-bin/mailman/listinfo/kplug-lpsg
