RFC on range design for D2

[Bill Baxter]

On Thu, Sep 11, 2008 at 1:31 PM, Benji Smith <dlanguage at benjismith.net> wrote:
> Bill Baxter wrote:
>>
>> Ok, but I have yet to hear an actual use case that demands blazing
>> fast iteration both forwards and backwards.  In your shuffling video
>> there's no way moving the iterator back and forth is going to be the
>> bottleneck.  In my undo/redo stack example it is also far from being
>> on the critical path.    I think it goes back to the fact that going
>> back and forth randomly isn't a property of many algorithms.  In all
>> the examples I can think of it's more a property of how humans
>> interact with data.  And humans are slow compared to how long it takes
>> to update a few extra values.
>
> Oh!! I thought of one!!
>
> Parsers & regex engines move both forward and backward, as they try to match
> characters to a pattern.
>
> Really, anything that uses an NFA or DFA to define patterns would benefit
> from fast bidirectional iteration...

Good call.  I was about to post something mentioning that Turing
machines but that seemed too academic.  Same class of thing as
NFA/DFA/FSM.

The question is, though, would you really implement those things using
a linked list?  I would expect most of those suckers work on arrays,
and so can take advantage of the bidirectional nature of random access
ranges.

Hmm, for FSMs you can't really define a good end state.  There may not
be any particular end state. ... ah, but wait I forgot.  That's the
beauty of a range -- the end "state" doesn't have to be a "state" per
se.  It can be any predicate you want it to be.  "Range" is misleading
in this case.  This is one of those cases where you just have to
remember "range" means "current value plus stopping criterion".

--bb