It just occurred to me that about half the list thinks I just reinvented parser combinators. Not exactly; the thing that distinguishes regexes in particular, and the one whose implications I can't quite wrap my brain around, is that the "many" combinator is actually

> many' = reverse . many

But is it really that simple, and is an implementation with decent performance and space characteristics really that simple?  Or does something have to be designed from scratch around longest match semantics to get decent behavior?  (There's an analogy to folds here.  Using this in place of Parsec would have terrible space leaks....)