Regular Expression Matching using Partial Derivatives

Regular expression matching is a classical and well-studied problem.
Prior work applies DFA and Thompson NFA methods for the construction
of the matching automata. We propose the novel use of derivatives and
partial derivatives for regular expression matching.
We show how to obtain algorithms for various
matching policies such as POSIX and greedy left-to-right.
Our benchmarking results show that the run-time performance is promising
and that our approach can be applied in practice.

This is a topic, Kenny and I have pursued for quite a while and we have finally
managed to write up the ideas.
Here's the link to the paper
The implementation is on hackage. See regex-pderiv
[Edit: regex-pderiv replaces xhaskell-library]

Tag-free Combinators for Binding-Time Polymorphic Program Generation

Peter Thiemann and I have written a paper on (off-line) partial evaluation for polymorphic languages using GHC's advanced typing features.

The source code of the combinators is available here.

Here's the abstract:

Binding-time polymorphism enables a highly flexible binding-time analysis for offline partial evaluation. This work provides the tools to translate this flexibility into efficient program specialization in the context of a polymorphic language.

Following the cogen-combinator approach, a set of combinators is defined in Haskell that enables the straightforward transcription of a binding-time polymorphic annotated program into the corresponding program generator. The typing of the combinators mimics the constraints of the binding-time analysis. The resulting program generator is safe, tag-free, and it has no interpretive overhead.