Re: why are there [v e c t o r s] in Lisp?

[Barry Margolin <barmar@alum.mit.edu>]

In article <mailman.428.1444957396.7904.help-gnu-emacs@gnu.org>,
 Emanuel Berg <embe8573@student.uu.se> wrote:

> One of the things I like the most with Lisp is the way
> it is typed and written. It is just so much more
> enjoyable both to type and read. And otherwise
> interact with (e.g., the help). Long words are
> prefered, with everything spelled out - compare
> `gnus-action-message-log' to the argc, argv, etc.
> of typical C! Also dashes instead of the ugly
> underscore, which is less readable, and slower as well
> (two keys instead of one for the dash) - and then to
> think of the worst case, the CamelCase of Java (no pun
> intended - still, better keep the sick bags nearby!).
> And then while not exactly ugly, who needs the curly
> braces to delimit functions (virtually all other
> languages, apparently), or for that matter the square
> brackets of array indexes and iteration? Or the
> semi-colon to delimit expressions and statements?
> They are just a bit tricky to type (except for the
> semi-colon) and they make the code look like an
> anthill - for no reason as Lisp shows. But there is
> one thing that clouds the perfect sky - vectors.
> I realized this when I was thinking about this. Why is
> there a special syntax for vectors? In linear algebra,
> an n-dimensional vector is a sequence of n numbers,
> and collectively they make for something that has
> direction and magnitude (in particular, it doesn't
> have a position). But whatever the math, isn't that (a
> sequence of numbers) something that the lists of Lisp
> can handle just as well, or actually better, as it
> will be more generic (a lot of stuff that doesn't work
> on "real" Lisp vectors will work on vectors that are
> also lists). And using lists doesn't mean nobody
> cannot write hundreds of "math vector" specific stuff
> to modify those list vectors! Right?
> 
> Have a look:
> 
>     (vectorp [1 2 3]) ; t
> 
>     (vectorp '(1 2 3)) ; nil - really?

Lists and vectors have different performance characteristics. With 
lists, it's easy to insert and delete elements anywhere in the sequence, 
you just add another cons in the cdr chain, but accessing the nth 
element is O(n). With vectors, inserting and deleting is expensive, 
because you have to shift all the following elements over to make room 
(and appending may require moving the whole thing, because you didn't 
allocate enough room in the original location), but accessing the nth 
element can be done in constant time.

So lists are good for flexible data structures that you typically access 
linearly, while vectors are good for random-access data. Also, because 
vectors are stored in contiguous memory, they generally exhibit better 
locality -- this was more important in the days when RAM was expensive 
and limited, because paging was more likely when you had a large working 
set.

-- 
Barry Margolin, barmar@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***