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)))
