jaror, 10 months ago

@mangoiv perhaps it is slightly easier to read like this?

data RE = Empty | Eps | Ch Char | App RE RE | Alt RE RE | Star RE

data REalg a = REalg
  { emp :: a
  , eps :: a
  , ch :: Char -> a
  , app :: a -> a -> a
  , alt :: a -> a -> a
  , star :: a -> a
  }

foldRE :: REalg a -> RE -> a
foldRE alg = go where
  go = case
    Empty -> emp alg
    Eps -> eps alg
    Ch c -> ch alg c
    App p q -> app alg (go p) (go q)
    Alt p q -> alt alg (go p) (go q)
    Star p -> star alg (go p)

recognise :: RE -> StateT String [] ()
recognise = foldRE REalg
  { emp = empty
  , eps = pure ()
  , ch = c -> StateT (case x : xs | c == x -> [((), xs)]; _ -> [])
  , app = (*>)
  , alt = (<|>)
  , star = p -> fix (t -> p *> t <|> pure ())
  }