Email list hosting service & mailing list manager


Re: Why vectors? Derick Eddington 12 Aug 2008 00:34 UTC

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
----------------------------------------------------------------