%
% Este ficheiro contem um texto em Literate Haskell
%    Partes do ficheiro são texto em LaTeX e outras em Haskell
%    
%  Métodos de Programação III
%

\documentclass[12pt]{article}

\usepackage[portuges]{babel}
\usepackage[latin1]{inputenc}

%\usepackage{a4wide}
%\usepackage{graphics}
%\usepackage{graphicx}
%\usepackage{color}
\usepackage{alltt}
%\usepackage{latexsym}
%\usepackage[dvips]{epsfig}

\def\Ipe#1{\def\IPEfile{#1}\input{#1}}
\def\hask{\textsf{Haskell}}
\def\hugs{\textsf{Hugs}}

\newenvironment{code}
{\vspace{0.3cm}
\textbf{Código Haskell} \hspace{1cm} \hrulefill \\ 
\smallskip 
\begin{center}
\begin{minipage}{.80\textwidth} 
\begin{alltt}\small}
{\end{alltt}
\end{minipage}
\end{center}
\hrule\smallskip
}

\newtheorem{exercicio}{Exercício}[section]

\title{Métodos de Programação III\\ LESI + LMCC (3º ano)}
\author{Ficha Teórico-Prática nº 2\\ (Expressões Regulares (2))}
\date{Ano lectivo 2003/2004}
%\date{\today}

%-------------------- Inicio do Documento -------------------------------

\begin{document}

\maketitle

\noindent Este texto está escrito em \textbf{Literate Haskell}. Isto é, pode ser
interpretado como um documento \LaTeX\ ou como um puro programa na
linguagem \hask.\\
O documento é obtido "compilando"\  este ficheiro em
\LaTeX: \begin{center}\texttt{latex mp303f02.lhs}\end{center}
O programa \hask\ incluído neste
ficheiro é compilado/interpretado directamento pelos
compiladores/interpretadores de \hask, executando por exemplo o comando:
\begin{center}\texttt{hugs mp303f02.lhs}\end{center}
 Para isso o código \hask\
deve estar delimitado pelos comandos \verb@\@\texttt{begin\{code\}} e \verb@\@\texttt{end\{code\}}.\\\\
Responda às perguntas sobre \hask\ neste próprio
ficheiro para assim produzir o programa e a sua documentação.

\section{Expressões Regulares}
Sejam $\alpha$, $\beta$ e $\gamma$ expressões regulares, então podemos
afirmar que:

\begin{enumerate}
\item $(\alpha + \beta) + \gamma = \alpha + (\beta + \gamma)$

\item $\alpha + \emptyset = \emptyset + \alpha = \alpha$

\item $\alpha + \beta = \beta + \alpha$

\item $\alpha + \alpha = \alpha$

\item $(\alpha \beta) \gamma = \alpha (\beta \gamma)$

\item $\alpha \epsilon = \epsilon \alpha = \alpha$

\item $\alpha (\beta + \gamma) = \alpha \beta + \alpha \gamma$

\item $(\beta + \gamma) \alpha = \beta \alpha + \gamma \alpha$

\item $\alpha^+ = \alpha \alpha^* = \alpha^* \alpha$

\item $\alpha^* = \epsilon + \alpha^+$

\item $(\alpha + \epsilon)^+ = (\alpha + \epsilon)^* = \alpha^*$
\end{enumerate}

\begin{exercicio} 
Prove as seguintes igualdades:
\begin{enumerate}
\item $b^+ + (b^+ + \epsilon) b = b^+$

\item $a^* (b + cd) b^* = a^*b^+ + a^*cd + a^*cdb^+$

\item $a + a^+ = a^+$
\end{enumerate}
\end{exercicio}
%--------------------

\begin{exercicio} 
Simplifique as seguintes expressões regulares:
\begin{enumerate}
\item $a  (a^*b + c) a + a^+ba$

\item $l + l (l + d)^*$
\end{enumerate}
\end{exercicio}
%--------------------

\begin{exercicio} \label{exerc:erequiv}
Mostre que as expressões regulares $p = (ab + \epsilon)^+ ab + a(a^* +
bc) c^*$ e $q = abc^+ + a^+c^* + (ab)^*$ não são equivalentes.\\
Dê um
exemplo de uma frase $\alpha$ da linguagem definida pela expressão
regular $q$, mas que não é da linguagem definida por $p$, i.e.,
$\alpha \in {\cal L} (q)$ e $\alpha \notin {\cal L} (p)$.
\end{exercicio}
%--------------------

\section{Expressões Regulares em \hask}
Considere o  código \hask\ seguinte que define o tipo de dados \texttt{RegExp}
e a função associada \texttt{showRE}, desenvolvidos na aula anterior, bem como as expressões
regulares \texttt{digitos, int e int'} que especificam as linguagens dos digitos e dos
inteiros.\\
\newpage
\begin{code}
--
-- Módulo de Expressões Regulares em Haskell
--
-- Métodos de Programação III
-- 2000/2001
--

module RegExp where

data RegExp = Epsilon
            | Literal   Char
            | Or        RegExp RegExp
            | Then      RegExp RegExp
            | Star      RegExp 
            | OneOrMore RegExp    
            | Optional  RegExp
            deriving Show

showRE :: RegExp -> String 
showRE Epsilon = "&"
showRE (Literal l) = [l]
showRE (Or re1 re2) = "(" ++ (showRE re1) ++ "|" ++ (showRE re2) ++ ")" 
showRE (Then re1 re2) = "(" ++ (showRE re1) ++ (showRE re2) ++ ")" 
showRE (Star re1) = "(" ++ (showRE re1) ++ ")" ++ "*" 
showRE (OneOrMore re1) = "(" ++ (showRE re1) ++ ")" ++ "+" 
showRE (Optional re1) = "(" ++ (showRE re1) ++ ")" ++ "?" 

digitos = (Literal '0') `Or` (Literal '1') `Or` (Literal '2') `Or` 
          (Literal '3') `Or` (Literal '4') `Or` (Literal '5') `Or`
          (Literal '6') `Or` (Literal '7') `Or` (Literal '8') `Or`
          (Literal '9')  

int     = (Epsilon `Or` ((Literal '-') `Or` (Literal '+')))
          `Then` (digitos `Then` Star digitos)

int'    = (Optional ((Literal '-') `Or` (Literal '+')))
          `Then` (OneOrMore digitos)
\end{code}
\newpage
\begin{exercicio} 
Atendendo à assinatura apresentada e ao código já escrito abaixo,
complete a definição da função \texttt{matches} que verifica se uma dada frase (\emph{string}) pertence 
à linguagem gerada por uma dada expressão regular.

\begin{code}
matches :: RegExp -> String -> Bool
matches Epsilon inp        = 
matches (Literal l) inp    =  
matches (Or re1 re2) inp   = 
matches (Then re1 re2) inp =  
matches (Star re) inp      = matches Epsilon inp ||
                             or [ matches re s1 && matches (Star re) s2 
                                | (s1,s2) <- frontSplits inp ]

splits :: [a] -> [ ([a],[a]) ]
splits s = [ splitAt n s | n <- [ 0 .. length s ] ]

frontSplits :: [a] -> [ ([a],[a]) ]
frontSplits s = [ splitAt n s | n <- [ 1 .. length s ] ]

\end{code}
\end{exercicio}
%--------------------

\begin{exercicio}
Tomando em consideração as definições anteriores,
escreva o código \hask\ para definir a função
\texttt{isInt} que, dada uma string
$\alpha$, "diz" se $\alpha$ é um inteiro ou não. Isto é, tem tipo
\texttt{isInt :: String -> Bool}.

\begin{code}

isInt :: String -> Bool
isInt  = 

\end{code}
\end{exercicio}
%--------------------

\begin{exercicio}
Considere as expressões regulares $p$ e $q$ do exercício
\ref{exerc:erequiv}. Escreva, então, essas expressões regulares em \hask\ e
defina a função \texttt{xxx} que tem como argumento uma frase e dá
verdade se a frase pertence a ambas as linguagens definidas pelas
expressões regulares e falso caso contrário. Use a frase $\alpha$
definida no exercício \ref{exerc:erequiv} para provar em \hask\ que
$p$ e $q$ não são equivalentes.

\begin{code}

xxx :: String -> Bool
xxx  = 

\end{code}
\end{exercicio}
%--------------------

\begin{exercicio}
O tipo de dados \texttt{RegExp} apresentado já contém os constructores
para modelar os usuais operadores \textit{opcional} e \textit{uma ou mais
repetições}, tal como se tinha proposto no fim da ficha anterior. Como então se disse, 
trata-se de uma \emph{definição extendida de expressão regular}.\\
Porém, a função \texttt{matches} só está definida para os operadores básicos e se por exemplo aceita
a expressão \texttt{int} como argumento, já dá erro se invocada com \texttt{int'}.
Para se poder usar essa função em qualquer caso, é necessário primeiro converter
uma expressão regular \textit{extendida} para a sua forma canónica
(isto é, definida pelos cinco constructores iniciais).\\
Escreva, então, uma função \texttt{extREtoRE} que realize a referida conversão de expressões regulares.
Depois de o fazer, verifique que já pode usar a função \texttt{matches'} definida abaixo.

\begin{code}

-- extREtoRE: RegExp -> RegExp
-- extREtoRE = 

-- matches' = matches . extREtoRE

\end{code}
\end{exercicio}
%--------------------

\begin{exercicio}
Considere as funções \texttt{extREtoRE} e  \texttt{showRE}
definida atrás. Ambas as funções apresentam o mesmo
padrão de recursividade: a recursividade segue a estrutura do tipo de
dados \texttt{RegExp}.\\
Recorde que na cadeira de \textsf{Métodos de
Programação I} foram apresentados os \emph{catamorfismos} para modelar estes
padrões de recursividade.
Nesse contexto pretende-se que:\\\\\\
\begin{enumerate}
\item Derive o catamorfismo para o tipo de dados indutivo \texttt{RegExp}\\
\begin{code}


\end{code}

\item Re-escreva as funções \texttt{extREtoRE} e \texttt{showRE} como catamorfismos.\\
\begin{code}


\end{code}

\end{enumerate}
\end{exercicio}
%--------------------

\end{document}