<div dir="ltr">Thank you so much for pointing me to this paper. What an absolute gem it is! Efficiently evaluating regex with a recursive ADT instead of a graph puts me one step closer to a solution. In my problem domain, regex frequently are mostly sequences at the top level. That is, these are common:<div><br></div><div>    The number [0-9]* is a good number</div><div>    I have [0-9]* pupp(ies|y).</div><div><br></div><div>This are not:</div><div><br></div><div>    (Hello|from|the|other|side)*</div><div><br></div><div>Using the paper's terminology, I think I should be able to have a `FingerTree X REG` (for some X I'm not sure of), where every top-level sequence is represented as adjacent elements in the finger tree. I'm not sure if this will actually work, but it seems plausible that it will.</div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Fri, Mar 1, 2019 at 3:55 AM Sergey Vinokurov <<a href="mailto:serg.foo@gmail.com">serg.foo@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Modifying regular expressions reminds me of the great functional pearl<br>
called 'A Play on Regular Expressions'. Perhaps this is the approach you<br>
were thinking about?<br>
<br>
Sergey<br>
<br>
On 28/02/2019 18:43, Andrew Martin wrote:<br>
> Greetings,<br>
> <br>
> In Dan Piponi's blog post Fast Incremental Regular Expression Matching<br>
> with Monoids [1], he outlines a way to take advantage of fingertrees to<br>
> perform increment regex matching. In his article, the regular expression<br>
> (more accurately, its equivalent DFA) is fixed, and the strings we are<br>
> matching on are modified incrementally. What I'm interested in is the<br>
> opposite: What if the regular expression is modified incrementally and<br>
> the string we are testing is static?<br>
> <br>
> Thinking about this, it seems to run into problems immediately.<br>
> Typically, to evaluate a regular expression, I would convert it to a NFA<br>
> (and then maybe to a DFA). But there is no way to do incremental graph<br>
> modification on the resulting graphs. (Or is there?). And even if there<br>
> were a way, it seems unclear how one would go about exploiting its<br>
> incremental nature. To provide an example, consider the following regex<br>
> and sample string:<br>
> <br>
> Regex: Lost (dog|cat) loo for home<br>
> Sample: Lost dog looking for home<br>
> <br>
> In the regex, I'm currently in the middle of typing "looking", so it<br>
> doesn't match the sample string. But large parts of it do. So when I<br>
> update the regex by typing "k", I'd like to be able to not redo this<br>
> work. Maybe there's a certain subset of regex that's amenable to this<br>
> kind of incremental evaluation. Maybe not. If anyone has any additional<br>
> insights or can point me to any research, I would appreciate it greatly.<br>
> Thanks.<br>
> <br>
> [1] <a href="http://blog.sigfpe.com/2009/01/fast-incremental-regular-expression.html" rel="noreferrer" target="_blank">http://blog.sigfpe.com/2009/01/fast-incremental-regular-expression.html</a><br>
> <br>
> <br>
> -- <br>
> -Andrew Thaddeus Martin<br>
> <br>
> _______________________________________________<br>
> Libraries mailing list<br>
> <a href="mailto:Libraries@haskell.org" target="_blank">Libraries@haskell.org</a><br>
> <a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries</a><br>
> <br>
<br>
</blockquote></div><br clear="all"><div><br></div>-- <br><div dir="ltr" class="gmail_signature">-Andrew Thaddeus Martin</div>