CS计算机代考程序代写 \begin{code}

\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}