Regular expressions are truly elegant. If the regex engine is built in a functional (compositional style), it is even more elegant. This particular Functional

Regular expressions are truly elegant. If the regex engine is built in a functional (compositional style), it is even more elegant. This particular Functional pearl is my favorite, http://sebfisch.github.io/haskell-regexp/regexp-play.pdf http://sebfisch.github.io/haskell-regexp/regexp-play.pdf And my implementation of the same in scala (40 lines if you ignore some niceties, and its terribly fast asymptotically) https://gist.github.com/yellowflash/826004277874cadabbc502e6d406b39e https://gist.github.com/yellowflash/826004277874cadabbc502e6... For TLDR on the paper, It slowly builds an abstraction and implementation on regex engine which runs on O(mn) where m is length of the regex and n - length of the text. Then they generalize it to do grouping and even extend it to match context free grammar (using lazy evaluation mostly).