Chris Kuklewicz announced, enthusiastically, the release of haskell-regex-tdfa 1.0. You can now get the Arch Linux package for it here. Amongst the varied and many regex libs for Haskell regex-tdfa stands as being 100% Haskell (not a binding to a C library), and for its use in the Yi project.
To quote Chris on the 1.0 release:
I am proud of this release.
This is not just a bug fix release.
It is a serious improvement in the asymptotic running time.
The previous versions allowed bad combinations of pattern and searched text length to scale badly in the length of the text. Previously the worst case for text of length N was O(N^3).
The new worst case asymptotic runtime scaled as O(N).
There is never any backtracking.
And the worst case storage space is independent of N.
Good work, Chris, and thanks for all the regex packages.