I had some fun Haskelling Thompson's algorithm too: https://github.com/darius/sketchbook/blob/master/regex/nfave... -- though I think Haskell's at a disadvantage for this one.