Re: Too much of a good thing? Taylor Campbell 17 Apr 2003 01:57 UTC
On Tuesday, April 15, 2003, at 01:35 AM, Sergei Egorov wrote: > I'd rather cut it to one third, but then Olin will come out of > his lair and add the rest and then some :) Heheh. > The question is not whether LIST->VECTOR and VECTOR->LIST are > actually used in the implementation, but whether vector-specific > algorithms > you propose are better than just list operations followed by a > conversion > or the same operations on lists with no conversion at all. Did you > turn any > SRFI-1 algorithms into something more effective (from linear- to > constant-time, > from quadratic to linear etc.)? Oh, I see what you mean. (I missed the 'the performance is the same as' bit) In that case, I'm not really sure...it's been a while since I wrote the implementation, and my memory isn't that great. > For example, both vector search and list search are linear by number of > elements. > This means that there is no big insentive to use vectors if what you > want is > linear search. On the other hand, you can sort vectors and use binary > search: this is where vectors are much more effective. Thus, I would > expect vector SRFI to include BINARY-SEARCH and SORT! operations > (real benefits), but can easily do without linear search (writing one > more > DO loop is no big deal). I deliberately avoided writing anything involving sorting vectors, since SRFI 32 will provide that. However, I may later include a VECTOR-BINARY-SEARCH -- it merely didn't occur to me to do so previously. > Can you give me any pointers to drafts or notes on his project? http://www.sgmiller.org/srfi-44.html I'm in the process of writing the reference implementation. > Turns N-ary procedure into M-ary (M < K) by "fixing" or "binding" > values of some arguments. Hmm. Could you show me a definition of it, or an example of using it? > I wrote a draft myself long ago, but had no time to finish it. May be > this > discussion will move it up on my priority list... I'd love to see it. Where can I find a copy? > I guess it is fine too. > By the way, you forgot to mention VECTOR-COPY!'s behavior in case of > intra-vector copy (target and vec are the same). Does it copy to the > left, > to the right, or does it chose the "correct" direction automatically? If they are the same in terms of EQ?, or EQUAL? ? I assume the former. > True, but this somehow ligitimizes restrictive implementations. > I just consider them broken :) Unfortunately, some of the major ones, like CHICKEN, have this sort of restriction. But if you insist upon having VECTOR-APPEND instead of VECTOR-CONCATENATE[*] (please, someone: think up a better name than VECTOR-CONCATENATE*), then I'll agree. > Which everybody can easily define by composition (especially when > given a suitable high-order primitive). OK, then, show me your functional-ish SRFI thing! > More, if you take this road, > nothing prevents you from making VECTOR-APPEND-REVERSE, > VECTOR-CONCATENATE-REVERSE, > VECTOR-REVERSE-CONCATENATE and dozens of others. No, that's the C++ road, where you continue to add whatever you can possibly think of, even if it could never be useful in any situation whatsoëver. Of course, at first, I shamefully admit that this was the road taken, but I did certainly intend to make great cuts to the thing. > Personally, I dislike REDUCEs because while giving you certain > performance benefits in some imaginary cases (the dreadful database > queries!), > they allow you to "cheat" (or make an honest mistake) by giving an > inconsistent > KONS/ RIDENTITY pair. Try to copy a list with REDUCE and you will > see that it's not only a performance hack - it is a *broken* > performance > hack! Very well -- no VECTOR-REDUCE[-RIGHT]. > On the second thought, NO, unfolds are not very useful (no benefits > for vectors). Indeed. > Just compositions with VECTOR-COPY... OK. > Yes, with start and end; When there is only one vector argument, > they are easy to remember. Good, good. > That's your only option if you don't want to reallocate the vector > for performance reasons, but can afford the loss of some "old" > elements. Some "history" stacks, circular buffers of fixed size etc. > work this way. OK, I was just wondering if you had found them useful ever. > Start and End arguments are trouble... I'd prefer to have abstract > operations > that can work with "windows" over sequences as first-class objects. > I don't care much about operations taking any number of vectors, except > for the cases where people may expect them (MAP, FOR-EACH). What about other cases like VECTOR-FOLD[-RIGHT], VECTOR=, et cetera? (and that's another thing: should there be vector comparisons in this reduced SRFI? -- and, if so, I don't like the name VECTOR= -- I'd personally prefer VECTOR-EQUAL? or VECTOR=? or something. Has anyone else an opinion on this?)