Issues with custom ranges Wolfgang Corcoran-Mathe (19 Jul 2020 20:57 UTC)
|
||
(missing)
|
||
Re: Issues with custom ranges
Wolfgang Corcoran-Mathe
(20 Jul 2020 00:55 UTC)
|
||
Re: Issues with custom ranges
Wolfgang Corcoran-Mathe
(20 Jul 2020 02:06 UTC)
|
||
Re: Issues with custom ranges
John Cowan
(21 Jul 2020 00:18 UTC)
|
Issues with custom ranges Wolfgang Corcoran-Mathe 19 Jul 2020 20:57 UTC
Ranges which use arbitrary indexer functions have been a major source of "gotchas" with this SRFI. An indexer function can do anything with its arguments (the range's lower bound and an index), and it has been tricky to forsee all of the implications of this. As an example, here's the sample implementation of range-drop, as of today (edited for conciseness): (define (range-drop r count) (range (range-element-comparator r) (range-lower-bound r) (- (range-length r) count) (lambda (b n) ((range-indexer r) b (+ n count))))) The important detail here is that the indexer of the new subrange calls the original range's indexer with an offset. This has the annoying effect of causing iterated applications of range-drop (and other procedures which take the same approach) to build up a chain of indexers; range-ref, when called on the resulting range, will take time proportional to the length of the chain of indexers. So why not simply change the lower bound? (define (range-drop r count) (range (range-element-comparator r) (range-ref r count) ; new lower bound (- (range-length r) count) (range-indexer r))) ; same indexer as r The above works just fine for ranges created by the SRFI's numeric-range constructor, and, indeed, for any range whose indexer satisfies (indexer lower-bound n) = (indexer (indexer lower-bond n) 0) This doesn't hold in general, though; indexers may return radically different results when their first argument is changed. Other ideas which have been foiled by this include some optimizations for range-take-while and range-contains? which assume monotonic ranges. I'm not remotely confident that there aren't many bugs and edge-cases waiting to be discovered with arbitrary ranges. I think it might be in order to require a small set of properties to hold of an indexer function. I'd suggest the above equation as a start. -- Wolfgang Corcoran-Mathe <xxxxxx@sigwinch.xyz> "Nothing can transcend its smallest elements." --CEO Nwabudike Morgan