\begin{code}
{-# OPTIONS_GHC -Wall #-}
module Feb04 where
import Jan26
\end{code}
Learning objectives:
\begin{itemize}
\item Deep Embeddings – back to regular expressions
\end{itemize}
Deep Embedding: representing a language as a data-structure
Language of regular expressions:
\begin{code}
infixr 7 :|:
infixr 5 :*:
data RE =
Eps
| Ch Char
| RE :|: RE
| RE :*: RE
| St RE
| Plus RE
deriving (Eq, Show)
toRecog :: RE -> RegExp
toRecog Eps = eps
toRecog (Ch c) = char c
toRecog (e1 :|: e2) = toRecog e1 ||| toRecog e2
toRecog (e1 :*: e2) = toRecog e1 <**> toRecog e2
toRecog (St e) = star (toRecog e)
toRecog (Plus e) = toRecog (e :*: St e)
\end{code}
What can we do with this now?
\begin{code}
enumerate :: RE -> [ String ]
enumerate Eps = [ “” ]
enumerate (Ch d) = [ [d] ]
enumerate (e1 :|: e2) = enumerate e1 `interleave` enumerate e2
enumerate (_ :*: _) = [] — will be enumerate e1 `cartesian` enumerate e2
enumerate (St _) = [] — wrong
enumerate (Plus e) = enumerate (e :*: St e)
interleave :: [a] -> [a] -> [a]
interleave [] ys = ys
interleave (x:xs) ys = x : interleave ys xs — note the swap!!!!
\end{code}
Can we do it on |RegExp| ? Yes! Massively inefficiently. |String -> Bool|