[Haskell-cafe] regex-applicative library needs your help! (algorithmic challenge)

[Anton Tayanovskyy]

> I like the approach of Russ Cox[2]. One of the great ideas there (which I
> think he didn't emphasize enough) is to have a queue which allows O(1)
> testing whether an element is already there [3]. This solves the problem
> with priorities -- the states are guaranteed to be enqueued in the order
> of their priorities, and there are no repetitions.

Hm, this sounds great! So then the number of states is just the size
of the NFA, so the memory does not depend on the input string length?
Have you tried this approach yet? I wouldn't vouch for my code in that
gist, I kind of remember trying to eliminate the duplicates while
preserving order buy not sure if I did it correctly there.

>
> To be able to process the states in the proper order I'll have to give
> up Glushkov automaton and probably use something similar to your
> construction [4].
>
> [2] http://swtch.com/~rsc/regexp/regexp2.html
> [3] http://code.google.com/p/re2/source/browse/util/sparse_array.h
> [4] http://t0yv0.blogspot.com/2011/07/combinatory-regular-expressions-in.html
>
> --
> Roman I. Cheplyaka :: http://ro-che.info/
>



-- 
Kind Regards,
Anton Tayanovskyy

WebSharper™ - type-safe JavaScript in F#
http://intellifactory.com