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

Re: Why vectors?

This page is part of the web mail archives of SRFI 99 from before July 7th, 2015. The new archives for SRFI 99 contain all messages, not just those from before July 7th, 2015.

On Mon, 2008-08-11 at 15:57 -0700, Elf wrote:
> 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.

I think you are misunderstanding what I'm suggesting.  I'm only
suggesting that the API to the four procedures make-rtd,
rtd-constructor, rtd-field-names, and rtd-all-field-names use lists
instead of vectors for the field specifiers given to or returned from
those procedures.

: Derick