Depends on the parser combinator library. Real regexes can be matched in time linear in the input size; you'll need to use an applicative parser combinator lik

Depends on the parser combinator library. Real regexes can be matched in time linear in the input size; you'll need to use an applicative parser combinator like regex-applicative (https://hackage.haskell.org/package/regex-applicative https://hackage.haskell.org/package/regex-applicative) to get that kind of asymptotic complexity. A monadic one like Parsec is impossible to analyze statically to turn into a finite automaton.