Lisp collections

From: Chris Capel (ch.ris_at_iba.nktech.net)
Date: 09/21/04 

Date: Mon, 20 Sep 2004 22:04:01 -0500

Coming from a C# background, one thing I've begun to miss in lisp is a nice,
flexible array/collection feature. Let me describe the .NET ArrayList class.

It's built over a fixed-length array that's reallocated and copied when you
add elements over the maximum length. You access the elements through an
index, like a normal array. You can add any object as a member, and remove
an object based on the object itself or its index. You can get the number
of members in the array, and do various resizing things on it.

Has anyone written a library for this in Lisp?

I hear a lot that in Lisp, you should use lists, and then switch to arrays
when you need performance. But it seems to me that lists don't offer many
of the features of the ArrayList (or even Lisp arrays). For one, there's the
the whole structure issue that means you can't change the first element of
a list referenced by a symbol without having the symbol. For two, you can't
easily add elements to the end without writing a util function (though
there is push--but there again is the structure issue). For three, CAR,
CDR, and CONS. I don't want to think about those. I don't want a binary
tree of cons cells. I don't even want a list. What is a list variable? A
variable whose value is a cons cell whose cdr points to nil or another cons
cell. No, no, no. I want a collection of objects. I want an ArrayList. I
want /abstraction/.

What sort of solution do people use in this situation?

Granted, lisp arrays are a good start. Fill-pointer offers about the same
thing as an array-list, except for the automatic resizing when you fill up
the currently allocated space. And the functions have funny names, too.

OK, now for the big picture. .NET has the idea of "collections"[1], about
the same as a Lisp sequence, I guess, only it's more consistently used. In
C#, any collection (really, any IEnumerable, but ICollection implements
that) can be iterated over using a "foreach". Why can't you do this in
Lisp? Because the basic types aren't CLOSsy enough. Can you iterate over
any sequence? It seems to me that list, hashtable, and vector types ought
to inherit from enumerable-collection, and foreach should be a generic
method on that. (A hashtable would return a key-value pair for every
iteration.) MAPCAR and friends should be defined in terms of this generic
"collection" idea, so they wouldn't be limited to lists. You could still
get a guaranteed enumeration order, but the order would be a property of
the type's enumerator. I'm sure there are other ways to make this idea more
pervasive than it currently seems to be in Lisp.

Just to be clear, I'm not advocating changing the language or the standard.
And I know that a lot of this can be taken care of with the consistent use
of a few good macros and a class or two. And I know that I could be
completely wrong. I'm just comparing what I know to what I'm learning. So,
am I alone in this dim opinion of Lisp collections?

Chris Capel

[1] Unordered, key can be anything. These are implemented using interfaces
(like COM or java) on every class that wants to be a collection, including
basic arrays and such. There's also a "list" interface, which is an ordered
collection indexable with integers, and about as pervasive as the
collection interface.

Relevant Pages

  • Re: functional style compared to procedural style and comments on a Mathematica function I saw.
    ... decent book on matrix computations. ... which of the many other compression techniques in the literature for sparse arrays you think is superior and how they should be represented in lisp? ... Which you can use in Mathematica but not in Lisp. ... That is Owith lists and Owith an array of arrays. ...
    (sci.math.symbolic)
  • Re: Cons cell archaic!?
    ... How would the implementation of a Lisp without a using cons look like? ... the irregularity in its often cited regular syntax. ... Lisp at core is based on functional programing on lists. ...
    (comp.lang.lisp)
  • Re: Cons cell archaic!?
    ... Lisp at core is based on functional programing on lists. ... instead of linked lists to represent formal lists as defined by the ... neurons, the pencil or ink on paper, the daisy chain of CONS cells, ...
    (comp.lang.lisp)
  • Re: How powerful macros are?
    ... >> for software engineers to use arrays for everything, ... Did I miss something or is #an impossibly unbearable syntax in Lisp? ... and arrays are often slower for very short lists. ... I've also extended the language so that I have re-readable hash tables ...
    (comp.lang.lisp)
  • Re: Cons cell archaic!?
    ... why lisp has the cons problem and was never ... langs that deal with lists, vast majority of list usage is just simple ... and if it's not done in those other languages it must be ... Java and Lisp as languages worth consiering, ...
    (comp.lang.lisp)