Haskell

5 readers

1 users here now

**The Haskell programming language community.** Daily news and info about all things Haskell related: practical stuff, theory, types, libraries, jobs, patches, releases, events and conferences and more... ### Links - Get Started with Haskell

founded 2 years ago

Brzozowski derivatives are neat, but good old denotational semantics of regular expressions can be very elegant too: (kbin.social)

submitted 2 years ago* (last edited 2 years ago) by jaror@kbin.social to c/haskell@kbin.social

5 comments fedilink hide all child comments

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

you are viewing a single comment's thread
view the rest of the comments

[–] jaror@kbin.social 1 points 2 years ago* (last edited 2 years ago) (1 children)

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 points 2 years ago (1 children)

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 points 2 years ago (1 children)

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

[–] jaror@kbin.social 1 points 2 years ago (1 children)

@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 points 2 years ago

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