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