[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Why vectors?



On Mon, 11 Aug 2008, Derick Eddington wrote:

On Mon, 2008-08-11 at 08:53 -0400, Physics wrote:
On Sun, 10 Aug 2008, Derick Eddington wrote:

interoperating with the R6RS records procedures that deal in vectors
without having to convert list<->vector is not a good enough reason
compared to the benefit of using lists with one's primary record system
of use,

What is the benefit of using lists?

The benefit of having the field specifiers of make-rtd, rtd-constructor,
rtd-field-names, and rtd-all-field-names be lists is: lists fit with all
the sequence-related things, both in standard Scheme and in others'
libraries, which use lists and not vectors.  E.g., memq for looking for
a field name, filter, append, reverse, etc.

Unless there's a compelling reason to use vectors, why not use Scheme's
natural sequence type: the list?

none of these is the most common usage of records: random field access. none of these really makes sense over a record-type, either.

random field access is O(1) for vectors. random field access is O(n) for lists.

creation of a new fixed-length vector is O(1).
creation of a new fixed-length list is O(n).

iteration and copy are O(n) for vectors.
iteration and copy are O(n) for lists.


specific records are not general-purpose data structures (though, like C structs, they can be used to incrementally build arbitrary data structures).

theres no need to memq for a field-name: theres a procedure that already
matches the field name, defined at record-definition time.

there is no concept of appending, and reversing would just throw everything
off.  what would filtering accomplish?

when you define a record, you already know what the field names are.  this
doesnt change.  you dont have to try to find it, its already there.

a way of looking at records (which is not correct in terms of why records
are useful) is that theyre mappings, like a hash table with a fixed
set of keys.  you already know whats in the table.  you defined all the names
already. you dont know what theyre pointing to, but the labels themselves are known. its a static set of keys, so you dont need to worry about whether
they'll still be there later or if new ones were added.  you just want to be
able to look up (or change) the value of something (which you have the label for) as quickly as possible. you want to be able to copy the thing as a whole
quickly.

lists are not an efficient or sensible way to implement such a thing. yes, there are all kinds of procedural manipulations you can do to
lists, but you wouldnt be doing anything like that to a record in the normal
scheme of things.  lists dont have a fixed size.  theyre an insanely flexible
datatype whose very structure can be changed trivially.  this is a wonderful
thing, but it doesnt match what is needed from records at all.

records dont change their structure; their entire set of fields and relations
are known definition time.  records are fixed-length; you cant grow em or
shrink em.  records need to support fast access; the fields are usually
used independently of each other.  vectors have all of these traits.

-elf