Stand back! haskell-regex-tdfa reaches 1.0.0

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.

About these ads

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s