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