jaror, (edited ) Brzozowski derivatives are neat, but good old denotational semantics of regular expressions can be very elegant too:
data RE = Empty | Eps | Ch Char | App RE RE | Alt RE RE | Star RE foldRE :: p -> p -> (Char -> p) -> (p -> p -> p) -> (p -> p -> p) -> (p -> p) -> RE -> p foldRE emp eps ch app alt star = go where go = case Empty -> emp Eps -> eps Ch c -> ch c App p q -> app (go p) (go q) Alt p q -> alt (go p) (go q) Star p -> star (go p) recognise :: RE -> String -> [String] recognise = foldRE (pure empty) pure (c -> case x : xs | c == x -> [xs]; _ -> []) (>=>) (liftA2 (<|>)) (p -> fix (t -> liftA2 (<|>) pure (p >=> t)))