\begin{code}
{-# OPTIONS_GHC -Wall #-}
module Feb08 where
import Jan26
import Feb04 hiding (enumerate)
\end{code}
Learning objectives:
\begin{itemize}
\item Deep Embeddings – back to regular expressions
\end{itemize}
\begin{code}
enumerate :: RE -> [ String ]
enumerate Eps = [ “” ]
enumerate (Ch d) = [ [d] ]
enumerate (e1 :|: e2) = enumerate e1 `interleave` enumerate e2
enumerate (e1 :*: e2) = enumerate e1 `cartesian` enumerate e2
enumerate (St e) = result
where — Laziness FTW!
result = [“”] ++ (enumerate e `cartesian` result)
enumerate (Plus e) = enumerate (e :*: St e)
cartesian :: [[a]] -> [[a]] -> [[a]]
cartesian [] _ = []
cartesian (x : xs) ys = [ x ++ y | y <- ys ] `interleave`cartesian xs ys
-- alternate? It "works" BUT it gets stuck on the first infinite list on the
-- xs side of things
cartesian' :: [[a]] -> [[a]] -> [[a]]
cartesian’ xs ys = [ x ++ y | x <- xs, y <- ys ]
lang3 :: RE
lang3 = St (Ch 'a' :|: Plus (Ch 'b' :|: Ch 'c'))
\end{code}
However, the type |RE| has some extra inhabitants there are not 'regular'
\begin{code}
anbn :: RE
anbn = Eps :|: (Ch 'a' :*: anbn :*: Ch 'b')
\end{code}
CHEATING! Using Haskell-level recursion to define things!
\begin{code}
anbn' :: RegExp
anbn' = eps ||| (char 'a' <**> anbn’ <**> char ‘b’)
\end{code}
We can simplify (redundant) REs.
Ex: (St (St e)) == St e
\begin{code}
simplify :: RE -> RE
simplify (St (St e)) = St e
simplify (Plus (St e)) = St e
simplify (St (Plus e)) = St e
simplify (Plus (Plus e)) = Plus e
simplify (e1 :|: e2)
| se1 == se2 = se1
| otherwise = se1 :|: se2
where se1 = simplify e1
se2 = simplify e2
simplify e = e
lang4 :: RE
lang4 = St (Ch ‘a’ :|: Ch ‘b’) :|: St (Ch ‘b’ :|: Ch ‘a’)
\end{code}