\begin{code}
{-# OPTIONS_GHC -Wall #-}
module Jan26 where
import Prelude hiding ((<*>))
\end{code}
Learning objectives:
\begin{itemize}
\item a first embedded language (regular expressions)
\item algebraic data types
\end{itemize}
A recognizer for languages. True if in, False if not.
\begin{code}
type RegExp = String -> Bool
eps :: RegExp
— eps s = s == “”
eps = (== “”)
char :: Char -> RegExp
char c = \s -> s == [c]
(|||) :: RegExp -> RegExp -> RegExp
e1 ||| e2 = \s -> e1 s || e2 s
\end{code}
Sequencing:
what does it mean that s is in \lstinline|e1 <*> e2| ?
means that s = (s0 s1 s2 …sn) (t0 t1 t2 … tk)
where si and tj are characters
where first part satisfies e1, second part satisfies e2
split : takes a list, and returns a list of \emph{all} (prefix, suffix) pairs
\begin{code}
split, split’, split” :: [a] -> [ ([a], [a]) ]
split [] = [ ([], []) ]
split (y : ys) = ([], y : ys) : [ (y : ps, qs) | (ps, qs) <- split ys ]
split' s = map (`splitAt` s) [0..length s]
split'' s = map (`splitAt` s) [1..length s]
(<*>) , (<**>) :: RegExp -> RegExp -> RegExp
e1 <*> e2 = \s -> or [ e1 x && e2 y | (x, y) <- split' s]
e1 <**> e2 = \s -> or [ e1 x && e2 y | (x, y) <- split'' s]
\end{code}
Difference: split\'\' skips the first match.
\begin{code}
star :: RegExp -> RegExp
star e = eps ||| (e <**> star e)
\end{code}
And now for some examples
\begin{code}
lang1 :: RegExp
lang1 = (char ‘a’ ||| char ‘b’) <**> star (char ‘c’)
lang2 :: RegExp
lang2 = star ((eps ||| char ‘d’) <*> char ‘x’)
lang3 :: RegExp
lang3 = (char ‘a’ ||| char ‘b’) <**> char ‘c’
\end{code}
Moving the algebraic types:
Note: ADT can be ‘algebraic data type’ OR ‘abstract data type’… and they
are COMPLETELY DIFFERENT.
Algebraic: given by explicit constructors; are all “sum of products”
Abstract: satisfies an interface
\begin{code}
data Expr =
Lit Integer
| Add Expr Expr
| Sub Expr Expr
deriving Show
ee1 :: Expr
ee1 = Add (Lit 5) (Sub (Lit 6) (Lit 12))
eval :: Expr -> Integer
eval (Lit i) = i
eval (Add e1 e2) = eval e1 + eval e2
eval (Sub e1 e2) = eval e1 – eval e2
\end{code}