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

#haskell