c/haskell · by jaror@kbin.social · 3y

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

1 points · 5 comments · view on lemmy.world

5 Comments

jaror@kbin.social · 1 pts · 3y (4 replies)

It's even nicer with Kleisli:

recognise' :: RE -> Kleisli [] String String
recognise' =
  foldRE empty id ch (>>>) (&lt;|>) (\p -> fix (\t -> id &lt;|> (p >>> t))) where
    ch c = Kleisli (\case x : xs | c == x -> [xs]; _ -> [])

jaror@kbin.social · 1 pts · 3y (3 replies)

Of course StateT is perhaps more common and as elegant as Kleisli:

recognise :: RE -> StateT String [] ()
recognise =
  foldRE empty (pure ()) ch (*>) (&lt;|>) (\p -> fix (\t -> p *> t &lt;|> pure ())) where
    ch c = StateT (\case x : xs | c == x -> [((), xs)]; _ -> [])

mangoiv@functional.cafe · 0 pts · 3y (2 replies)

@jaror I’d deem it more elegant if there were any useful names in here eh

jaror@kbin.social · 1 pts · 3y (1 reply)

@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 = (&lt;|>)
  , star = \p -> fix (\t -> p *> t &lt;|> pure ())
  }

mangoiv@functional.cafe · 1 pts · 3y

@jaror oh yeah much better. Lovely, thanks ;)