cp2324t.tex

\documentclass[11pt, a4paper, fleqn]{article}
\usepackage{cp2324t}
\makeindex

%================= lhs2tex=====================================================%
%% ODER: format ==         = "\mathrel{==}"
%% ODER: format /=         = "\neq "
%
%
\makeatletter
\@ifundefined{lhs2tex.lhs2tex.sty.read}%
  {\@namedef{lhs2tex.lhs2tex.sty.read}{}%
   \newcommand\SkipToFmtEnd{}%
   \newcommand\EndFmtInput{}%
   \long\def\SkipToFmtEnd#1\EndFmtInput{}%
  }\SkipToFmtEnd

\newcommand\ReadOnlyOnce[1]{\@ifundefined{#1}{\@namedef{#1}{}}\SkipToFmtEnd}
\usepackage{amstext}
\usepackage{amssymb}
\usepackage{stmaryrd}
\DeclareFontFamily{OT1}{cmtex}{}
\DeclareFontShape{OT1}{cmtex}{m}{n}
  {<5><6><7><8>cmtex8
   <9>cmtex9
   <10><10.95><12><14.4><17.28><20.74><24.88>cmtex10}{}
\DeclareFontShape{OT1}{cmtex}{m}{it}
  {<-> ssub * cmtt/m/it}{}
\newcommand{\texfamily}{\fontfamily{cmtex}\selectfont}
\DeclareFontShape{OT1}{cmtt}{bx}{n}
  {<5><6><7><8>cmtt8
   <9>cmbtt9
   <10><10.95><12><14.4><17.28><20.74><24.88>cmbtt10}{}
\DeclareFontShape{OT1}{cmtex}{bx}{n}
  {<-> ssub * cmtt/bx/n}{}
\newcommand{\tex}[1]{\text{\texfamily#1}}	% NEU

\newcommand{\Sp}{\hskip.33334em\relax}


\newcommand{\Conid}[1]{\mathit{#1}}
\newcommand{\Varid}[1]{\mathit{#1}}
\newcommand{\anonymous}{\kern0.06em \vbox{\hrule\@width.5em}}
\newcommand{\plus}{\mathbin{+\!\!\!+}}
\newcommand{\bind}{\mathbin{>\!\!\!>\mkern-6.7mu=}}
\newcommand{\rbind}{\mathbin{=\mkern-6.7mu<\!\!\!<}}% suggested by Neil Mitchell
\newcommand{\sequ}{\mathbin{>\!\!\!>}}
\renewcommand{\leq}{\leqslant}
\renewcommand{\geq}{\geqslant}
\usepackage{polytable}

%mathindent has to be defined
\@ifundefined{mathindent}%
  {\newdimen\mathindent\mathindent\leftmargini}%
  {}%

\def\resethooks{%
  \global\let\SaveRestoreHook\empty
  \global\let\ColumnHook\empty}
\newcommand*{\savecolumns}[1][default]%
  {\g@addto@macro\SaveRestoreHook{\savecolumns[#1]}}
\newcommand*{\restorecolumns}[1][default]%
  {\g@addto@macro\SaveRestoreHook{\restorecolumns[#1]}}
\newcommand*{\aligncolumn}[2]%
  {\g@addto@macro\ColumnHook{\column{#1}{#2}}}

\resethooks

\newcommand{\onelinecommentchars}{\quad-{}- }
\newcommand{\commentbeginchars}{\enskip\{-}
\newcommand{\commentendchars}{-\}\enskip}

\newcommand{\visiblecomments}{%
  \let\onelinecomment=\onelinecommentchars
  \let\commentbegin=\commentbeginchars
  \let\commentend=\commentendchars}

\newcommand{\invisiblecomments}{%
  \let\onelinecomment=\empty
  \let\commentbegin=\empty
  \let\commentend=\empty}

\visiblecomments

\newlength{\blanklineskip}
\setlength{\blanklineskip}{0.66084ex}

\newcommand{\hsindent}[1]{\quad}% default is fixed indentation
\let\hspre\empty
\let\hspost\empty
\newcommand{\NB}{\textbf{NB}}
\newcommand{\Todo}[1]{$\langle$\textbf{To do:}~#1$\rangle$}

\EndFmtInput
\makeatother
%
%
%
%
%
%
% This package provides two environments suitable to take the place
% of hscode, called "plainhscode" and "arrayhscode". 
%
% The plain environment surrounds each code block by vertical space,
% and it uses \abovedisplayskip and \belowdisplayskip to get spacing
% similar to formulas. Note that if these dimensions are changed,
% the spacing around displayed math formulas changes as well.
% All code is indented using \leftskip.
%
% Changed 19.08.2004 to reflect changes in colorcode. Should work with
% CodeGroup.sty.
%
\ReadOnlyOnce{polycode.fmt}%
\makeatletter

\newcommand{\hsnewpar}[1]%
  {{\parskip=0pt\parindent=0pt\par\vskip #1\noindent}}

% can be used, for instance, to redefine the code size, by setting the
% command to \small or something alike
\newcommand{\hscodestyle}{}

% The command \sethscode can be used to switch the code formatting
% behaviour by mapping the hscode environment in the subst directive
% to a new LaTeX environment.

\newcommand{\sethscode}[1]%
  {\expandafter\let\expandafter\hscode\csname #1\endcsname
   \expandafter\let\expandafter\endhscode\csname end#1\endcsname}

% "compatibility" mode restores the non-polycode.fmt layout.

\newenvironment{compathscode}%
  {\par\noindent
   \advance\leftskip\mathindent
   \hscodestyle
   \let\\=\@normalcr
   \let\hspre\(\let\hspost\)%
   \pboxed}%
  {\endpboxed\)%
   \par\noindent
   \ignorespacesafterend}

\newcommand{\compaths}{\sethscode{compathscode}}

% "plain" mode is the proposed default.
% It should now work with \centering.
% This required some changes. The old version
% is still available for reference as oldplainhscode.

\newenvironment{plainhscode}%
  {\hsnewpar\abovedisplayskip
   \advance\leftskip\mathindent
   \hscodestyle
   \let\hspre\(\let\hspost\)%
   \pboxed}%
  {\endpboxed%
   \hsnewpar\belowdisplayskip
   \ignorespacesafterend}

\newenvironment{oldplainhscode}%
  {\hsnewpar\abovedisplayskip
   \advance\leftskip\mathindent
   \hscodestyle
   \let\\=\@normalcr
   \(\pboxed}%
  {\endpboxed\)%
   \hsnewpar\belowdisplayskip
   \ignorespacesafterend}

% Here, we make plainhscode the default environment.

\newcommand{\plainhs}{\sethscode{plainhscode}}
\newcommand{\oldplainhs}{\sethscode{oldplainhscode}}
\plainhs

% The arrayhscode is like plain, but makes use of polytable's
% parray environment which disallows page breaks in code blocks.

\newenvironment{arrayhscode}%
  {\hsnewpar\abovedisplayskip
   \advance\leftskip\mathindent
   \hscodestyle
   \let\\=\@normalcr
   \(\parray}%
  {\endparray\)%
   \hsnewpar\belowdisplayskip
   \ignorespacesafterend}

\newcommand{\arrayhs}{\sethscode{arrayhscode}}

% The mathhscode environment also makes use of polytable's parray 
% environment. It is supposed to be used only inside math mode 
% (I used it to typeset the type rules in my thesis).

\newenvironment{mathhscode}%
  {\parray}{\endparray}

\newcommand{\mathhs}{\sethscode{mathhscode}}

% texths is similar to mathhs, but works in text mode.

\newenvironment{texthscode}%
  {\(\parray}{\endparray\)}

\newcommand{\texths}{\sethscode{texthscode}}

% The framed environment places code in a framed box.

\def\codeframewidth{\arrayrulewidth}
\RequirePackage{calc}

\newenvironment{framedhscode}%
  {\parskip=\abovedisplayskip\par\noindent
   \hscodestyle
   \arrayrulewidth=\codeframewidth
   \tabular{@{}|p{\linewidth-2\arraycolsep-2\arrayrulewidth-2pt}|@{}}%
   \hline\framedhslinecorrect\\{-1.5ex}%
   \let\endoflinesave=\\
   \let\\=\@normalcr
   \(\pboxed}%
  {\endpboxed\)%
   \framedhslinecorrect\endoflinesave{.5ex}\hline
   \endtabular
   \parskip=\belowdisplayskip\par\noindent
   \ignorespacesafterend}

\newcommand{\framedhslinecorrect}[2]%
  {#1[#2]}

\newcommand{\framedhs}{\sethscode{framedhscode}}

% The inlinehscode environment is an experimental environment
% that can be used to typeset displayed code inline.

\newenvironment{inlinehscode}%
  {\(\def\column##1##2{}%
   \let\>\undefined\let\<\undefined\let\\\undefined
   \newcommand\>[1][]{}\newcommand\<[1][]{}\newcommand\\[1][]{}%
   \def\fromto##1##2##3{##3}%
   \def\nextline{}}{\) }%

\newcommand{\inlinehs}{\sethscode{inlinehscode}}

% The joincode environment is a separate environment that
% can be used to surround and thereby connect multiple code
% blocks.

\newenvironment{joincode}%
  {\let\orighscode=\hscode
   \let\origendhscode=\endhscode
   \def\endhscode{\def\hscode{\endgroup\def\@currenvir{hscode}\\}\begingroup}
   %\let\SaveRestoreHook=\empty
   %\let\ColumnHook=\empty
   %\let\resethooks=\empty
   \orighscode\def\hscode{\endgroup\def\@currenvir{hscode}}}%
  {\origendhscode
   \global\let\hscode=\orighscode
   \global\let\endhscode=\origendhscode}%

\makeatother
\EndFmtInput
%
%%format (bin (n) (k)) = "\Big(\vcenter{\xymatrix@R=1pt{" n "\\" k "}}\Big)"


%------------------------------------------------------------------------------%


%====== DEFINIR GRUPO E ELEMENTOS =============================================%

\group{G19}
\studentA{102499}{Carlos Daniel Silva Fernandes}
\studentB{102497}{José Bernardo Moniz Fernandes}
\studentC{102504}{Pedro Augusto Camargo}

%==============================================================================%

\begin{document}
\sffamily
\setlength{\parindent}{0em}
\emergencystretch 3em
\renewcommand{\baselinestretch}{1.25} 
\input{Cover}
\pagestyle{pagestyle}

\newgeometry{left=25mm,right=20mm,top=25mm,bottom=25mm}
\setlength{\parindent}{1em}

\section*{Preâmbulo}

\CP\ tem como objectivo principal ensinar a progra\-mação de computadores
como uma disciplina científica. Para isso parte-se de um repertório de \emph{combinadores}
que formam uma álgebra da programação % (conjunto de leis universais e seus corolários)
e usam-se esses combinadores para construir programas \emph{composicionalmente},
isto é, agregando programas já existentes.

Na sequência pedagógica dos planos de estudo dos cursos que têm
esta disciplina, opta-se pela aplicação deste método à programação
em \Haskell, sem prejuízo da sua aplicação a outras linguagens
funcionais. Assim, o presente trabalho prático coloca os
alunos perante problemas concretos que deverão ser implementados em
\Haskell. Há ainda um outro objectivo: o de ensinar a documentar
programas, a validá-los e a produzir textos técnico-científicos de
qualidade.

Antes de abordarem os problemas propostos no trabalho, os grupos devem ler
com atenção o anexo \ref{sec:documentacao} onde encontrarão as instruções
relativas ao sofware a instalar, etc.

\begin{alert}
Valoriza-se a escrita de \emph{pouco} código, que corresponda a soluções
simples e elegantes mediante a utilização dos combinadores de ordem superior
estudados na disciplina.

Recomenda-se ainda que o código venha acompanhado de uma descrição de como
funciona e foi concebido, apoiado em diagramas explicativos. Para instruções
sobre como produzir esses diagramas e exprimir raciocínios de cálculo, ver
o anexo \ref{sec:diagramas}.
\end{alert}


\Problema

No passado dia 10 de Março o país foi a eleições para a Assembleia da República.
A lei eleitoral portuguesa segue, como as de muitos outros países, o chamado
\hondt{Método de Hondt} para selecionar os candidatos dos vários partidos, conforme
os votos que receberam. E, tal como em anos anteriores, há sempre 
\href{https://www.jn.pt/6761243323/mais-de-673-mil-votos-desperdicados-nas-legislativas}{notícias}
a referir a quantidade de votos desperdiçados por este método.
Como e porque é que isso acontece?

Pretende-se nesta questão construir em Hakell um programa que implemente
o método de Hondt. A \cne{Comissão Nacional de Eleições} descreve esse método
\hondt{nesta página}, que deverá
ser estudada para resolver esta questão. O quadro que aí aparece,

\qhondt

\noindent mostra o exemplo de um círculo eleitoral que tem direito a eleger 7 deputados e
onde concorrem às eleições quatro partidos \ensuremath{\Conid{A}}, \ensuremath{\Conid{B}}, \ensuremath{\Conid{C}} e \ensuremath{\Conid{D}}, cf:
\begin{hscode}\SaveRestoreHook
\column{B}{@{}>{\hspre}l<{\hspost}@{}}%
\column{E}{@{}>{\hspre}l<{\hspost}@{}}%
\>[B]{}\mathbf{data}\;\Conid{Party}\mathrel{=}\Conid{A}\mid \Conid{B}\mid \Conid{C}\mid \Conid{D}\;\mathbf{deriving}\;(\Conid{Eq},\Conid{Ord},\Conid{Show}){}\<[E]%
\ColumnHook
\end{hscode}\resethooks
A votação nesse círculo foi
\begin{hscode}\SaveRestoreHook
\column{B}{@{}>{\hspre}l<{\hspost}@{}}%
\column{E}{@{}>{\hspre}l<{\hspost}@{}}%
\>[B]{}[\mskip1.5mu (\Conid{A},\mathrm{12000}),(\Conid{B},\mathrm{7500}),(\Conid{C},\mathrm{4500}),(\Conid{D},\mathrm{3000})\mskip1.5mu]{}\<[E]%
\ColumnHook
\end{hscode}\resethooks
sendo o resultado eleitoral
\begin{hscode}\SaveRestoreHook
\column{B}{@{}>{\hspre}l<{\hspost}@{}}%
\column{E}{@{}>{\hspre}l<{\hspost}@{}}%
\>[B]{}\Varid{result}\mathrel{=}[\mskip1.5mu (\Conid{A},\mathrm{3}),(\Conid{B},\mathrm{2}),(\Conid{C},\mathrm{1}),(\Conid{D},\mathrm{1})\mskip1.5mu]{}\<[E]%
\ColumnHook
\end{hscode}\resethooks
apurado correndo
\begin{hscode}\SaveRestoreHook
\column{B}{@{}>{\hspre}l<{\hspost}@{}}%
\column{E}{@{}>{\hspre}l<{\hspost}@{}}%
\>[B]{}\Varid{result}\mathrel{=}\Varid{final}\;\Varid{history}{}\<[E]%
\ColumnHook
\end{hscode}\resethooks
que corresponde à última etapa da iteração:
\begin{hscode}\SaveRestoreHook
\column{B}{@{}>{\hspre}l<{\hspost}@{}}%
\column{12}{@{}>{\hspre}l<{\hspost}@{}}%
\column{E}{@{}>{\hspre}l<{\hspost}@{}}%
\>[B]{}\Varid{history}\mathrel{=}{}\<[12]%
\>[12]{}[\mskip1.5mu \for{\Varid{step}}\ {\Varid{db}}\;\Varid{i}\mid \Varid{i}\leftarrow [\mskip1.5mu \mathrm{0}\mathinner{\ldotp\ldotp}\mathrm{7}\mskip1.5mu]\mskip1.5mu]{}\<[E]%
\ColumnHook
\end{hscode}\resethooks
Verifica-se que, de um total de \ensuremath{\mathrm{27000}} votos, foram desperdiçados:
\begin{hscode}\SaveRestoreHook
\column{B}{@{}>{\hspre}l<{\hspost}@{}}%
\column{11}{@{}>{\hspre}l<{\hspost}@{}}%
\column{E}{@{}>{\hspre}l<{\hspost}@{}}%
\>[B]{}\Varid{wasted}\mathrel{=}{}\<[11]%
\>[11]{}\mathrm{9250}{}\<[E]%
\ColumnHook
\end{hscode}\resethooks

Completem no anexo \ref{sec:resolucao} as funções que se encontram aí
indefinidas\footnote{Cf.\ \ensuremath{\bot } no código.}, podendo adicionar funções
au\-xiliares que sejam convenientes. No anexo \ref{sec:codigo} é dado
algum código preliminar.

\Problema

A biblioteca \LTree\ inclui o algoritmo ``mergesort'' (\msort{\ensuremath{\Varid{mSort}}}), que é um hilomorfismo
baseado função
\begin{hscode}\SaveRestoreHook
\column{B}{@{}>{\hspre}l<{\hspost}@{}}%
\column{E}{@{}>{\hspre}l<{\hspost}@{}}%
\>[B]{}\Varid{merge}\mathbin{::}\Conid{Ord}\;\Varid{a}\Rightarrow ([\mskip1.5mu \Varid{a}\mskip1.5mu],[\mskip1.5mu \Varid{a}\mskip1.5mu])\to [\mskip1.5mu \Varid{a}\mskip1.5mu]{}\<[E]%
\ColumnHook
\end{hscode}\resethooks
que junta duas listas previamente ordenadas numa única lista ordenada.

Nesta questão pretendemos generalizar \ensuremath{\Varid{merge}} a \ensuremath{\Varid{k}}-listas (ordenadas),
para qualquer \ensuremath{\Varid{k}} finito:
\begin{hscode}\SaveRestoreHook
\column{B}{@{}>{\hspre}l<{\hspost}@{}}%
\column{E}{@{}>{\hspre}l<{\hspost}@{}}%
\>[B]{}\Varid{mergek}\mathbin{::}\Conid{Ord}\;\Varid{a}\Rightarrow [\mskip1.5mu [\mskip1.5mu \Varid{a}\mskip1.5mu]\mskip1.5mu]\to [\mskip1.5mu \Varid{a}\mskip1.5mu]{}\<[E]%
\ColumnHook
\end{hscode}\resethooks
Esta função deverá ser codificada como um hilomorfismo, a saber:
\begin{hscode}\SaveRestoreHook
\column{B}{@{}>{\hspre}l<{\hspost}@{}}%
\column{E}{@{}>{\hspre}l<{\hspost}@{}}%
\>[B]{}\Varid{mergek}\mathrel{=}\hyloList{\Varid{f}}{\Varid{g}}{}\<[E]%
\ColumnHook
\end{hscode}\resethooks
\begin{enumerate}
\item	Programe os genes \ensuremath{\Varid{f}} e \ensuremath{\Varid{g}} do hilomorfismo \ensuremath{\Varid{mergek}}.
\item	Estenda \ensuremath{\Varid{mSort}} a
\begin{hscode}\SaveRestoreHook
\column{B}{@{}>{\hspre}l<{\hspost}@{}}%
\column{E}{@{}>{\hspre}l<{\hspost}@{}}%
\>[B]{}\Varid{mSortk}\mathbin{::}\Conid{Ord}\;\Varid{a}\Rightarrow \Conid{Int}\to [\mskip1.5mu \Varid{a}\mskip1.5mu]\to [\mskip1.5mu \Varid{a}\mskip1.5mu]{}\<[E]%
\ColumnHook
\end{hscode}\resethooks
por forma a este hilomorfismo utilizar \ensuremath{\Varid{mergek}} em lugar de \ensuremath{\Varid{merge}} na estapa
de ``conquista". O que se espera de \ensuremath{\Varid{mSortk}\;\Varid{k}} é que faça a partição da lista
de entrada em \ensuremath{\Varid{k}} sublistas, sempre que isso for possível.
(Que vantagens vê nesta nova versão?)
\end{enumerate}

\Problema

Considere-se a fórmula que dá o \ensuremath{\Varid{n}}-ésimo \catalan{número de Catalan}:
\begin{eqnarray}
	C_n = \frac{(2n)!}{(n+1)! (n!) }
	\label{eq:cat}
\end{eqnarray}
No anexo \ref{sec:codigo} dá-se a função \ensuremath{\Varid{catdef}} que implementa a definição (\ref{eq:cat}) em Haskell.
É fácil de verificar que, à medida que \ensuremath{\Varid{n}} cresce, o tempo que \ensuremath{\Varid{catdef}\;\Varid{n}} demora a executar degrada-se.
 
Pretende-se uma implementação mais eficiente de $C_n$ que, derivada por recursividade mútua,
não calcule factoriais nenhuns:
\begin{hscode}\SaveRestoreHook
\column{B}{@{}>{\hspre}l<{\hspost}@{}}%
\column{E}{@{}>{\hspre}l<{\hspost}@{}}%
\>[B]{}\Varid{cat}\mathrel{=}\cdots \comp \for{\Varid{loop}}\ {\Varid{init}}\;\mathbf{where}\;\cdots {}\<[E]%
\ColumnHook
\end{hscode}\resethooks

No anexo \ref{sec:codigo} é dado um oráculo que pode ajudar a testar \ensuremath{\Varid{cat}}.
Deverá ainda ser comparada a eficiência da solução calculada \ensuremath{\Varid{cat}} com a de \ensuremath{\Varid{catdef}}.

\begin{alert}
\textbf{Sugestão}: Começar por estudar a regra prática que se dá no anexo
\ref{sec:mr} para problemas deste género.
\end{alert}

\Problema

Esta questão aborda um problema que é conhecido pela designação \emph{Largest
Rectangle in Histogram}. Precebe-se facilmente do que se trata olhando para a parte
esquerda da figura abaixo, que mostra o histograma correspondente à sequência numérica:
\begin{hscode}\SaveRestoreHook
\column{B}{@{}>{\hspre}l<{\hspost}@{}}%
\column{E}{@{}>{\hspre}l<{\hspost}@{}}%
\>[B]{}\Varid{h}\mathbin{::}[\mskip1.5mu \Conid{Int}\mskip1.5mu]{}\<[E]%
\\
\>[B]{}\Varid{h}\mathrel{=}[\mskip1.5mu \mathrm{2},\mathrm{1},\mathrm{5},\mathrm{6},\mathrm{2},\mathrm{3}\mskip1.5mu]{}\<[E]%
\ColumnHook
\end{hscode}\resethooks

\histograma

À direita da mesma figura identifica-se o rectângulo de maior área que é possível inscrever no referido histograma,
com área \ensuremath{\mathrm{10}\mathrel{=}\mathrm{2}\mathbin{*}\mathrm{5}}.

Pretende-se a definição de uma função em Haskell
\begin{hscode}\SaveRestoreHook
\column{B}{@{}>{\hspre}l<{\hspost}@{}}%
\column{E}{@{}>{\hspre}l<{\hspost}@{}}%
\>[B]{}\Varid{lrh}\mathbin{::}[\mskip1.5mu \Conid{Int}\mskip1.5mu]\to \Conid{Int}{}\<[E]%
\ColumnHook
\end{hscode}\resethooks
tal que \ensuremath{\Varid{lrh}\;\Varid{x}} seja a maior área de rectângulos que seja possível inscrever em \ensuremath{\Varid{x}}.

Pretende-se uma solução para o problema que seja simples e estruturada num hilomorfismo baseado num tipo indutivo estudado na disciplina ou definido \emph{on purpose}.

\newpage
\part*{Anexos}

\appendix

\section{Natureza do trabalho a realizar}
\label{sec:documentacao}
Este trabalho teórico-prático deve ser realizado por grupos de 3 alunos.
Os detalhes da avaliação (datas para submissão do relatório e sua defesa
oral) são os que forem publicados na \cp{página da disciplina} na \emph{internet}.

Recomenda-se uma abordagem participativa dos membros do grupo em \textbf{todos}
os exercícios do trabalho, para assim poderem responder a qualquer questão
colocada na \emph{defesa oral} do relatório.

Para cumprir de forma integrada os objectivos do trabalho vamos recorrer
a uma técnica de programa\-ção dita ``\litp{literária}'' \cite{Kn92}, cujo
princípio base é o seguinte:
%
\begin{quote}\em
	Um programa e a sua documentação devem coincidir.
\end{quote}
%
Por outras palavras, o \textbf{código fonte} e a \textbf{documentação} de um
programa deverão estar no mesmo ficheiro.

O ficheiro \texttt{cp2324t.pdf} que está a ler é já um exemplo de
\litp{programação literária}: foi gerado a partir do texto fonte
\texttt{cp2324t.lhs}\footnote{O sufixo `lhs' quer dizer
\emph{\lhaskell{literate Haskell}}.} que encontrará no \MaterialPedagogico\
desta disciplina des\-com\-pactando o ficheiro \texttt{cp2324t.zip}.

Como se mostra no esquema abaixo, de um único ficheiro (\ensuremath{\Varid{lhs}})
gera-se um PDF ou faz-se a interpretação do código \Haskell\ que ele inclui:

	\esquema

Vê-se assim que, para além do \GHCi, serão necessários os executáveis \PdfLatex\ e
\LhsToTeX. Para facilitar a instalação e evitar problemas de versões e
conflitos com sistemas operativos, é recomendado o uso do \Docker\ tal como
a seguir se descreve.

\section{Docker} \label{sec:docker}

Recomenda-se o uso do \container\ cuja imagem é gerada pelo \Docker\ a partir do ficheiro
\texttt{Dockerfile} que se encontra na diretoria que resulta de descompactar
\texttt{cp2324t.zip}. Este \container\ deverá ser usado na execução
do \GHCi\ e dos comandos relativos ao \Latex. (Ver também a \texttt{Makefile}
que é disponibilizada.)

Após \href{https://docs.docker.com/engine/install/}{instalar o Docker} e
descarregar o referido zip com o código fonte do trabalho,
basta executar os seguintes comandos:
\begin{Verbatim}[fontsize=\small]
    $ docker build -t cp2324t .
    $ docker run -v ${PWD}:/cp2324t -it cp2324t
\end{Verbatim}
\textbf{NB}: O objetivo é que o container\ seja usado \emph{apenas} 
para executar o \GHCi\ e os comandos relativos ao \Latex.
Deste modo, é criado um \textit{volume} (cf.\ a opção \texttt{-v \$\{PWD\}:/cp2324t}) 
que permite que a diretoria em que se encontra na sua máquina local 
e a diretoria \texttt{/cp2324t} no \container\ sejam partilhadas.

O grupo deverá visualizar/editar os ficheiros numa máquina local e compilá-los no \container, executando:
\begin{Verbatim}[fontsize=\small]
    $ lhs2TeX cp2324t.lhs > cp2324t.tex
    $ pdflatex cp2324t
\end{Verbatim}
\LhsToTeX\ é o pre-processador que faz ``pretty printing'' de código Haskell
em \Latex\ e que faz parte já do \container. Alternativamente, basta executar
\begin{Verbatim}[fontsize=\small]
    $ make
\end{Verbatim}
para obter o mesmo efeito que acima.

Por outro lado, o mesmo ficheiro \texttt{cp2324t.lhs} é executável e contém
o ``kit'' básico, escrito em \Haskell, para realizar o trabalho. Basta executar
\begin{Verbatim}[fontsize=\small]
    $ ghci cp2324t.lhs
\end{Verbatim}

\noindent O grupo deve abrir o ficheiro \texttt{cp2324t.lhs} num editor da sua preferência
e verificar que assim é: todo o texto que se encontra dentro do ambiente
\begin{quote}\small\tt
\text{\ttfamily \char92{}begin\char123{}code\char125{}}
\\ ... \\
\text{\ttfamily \char92{}end\char123{}code\char125{}}
\end{quote}
é seleccionado pelo \GHCi\ para ser executado.

\section{Em que consiste o TP}

Em que consiste, então, o \emph{relatório} a que se referiu acima?
É a edição do texto que está a ser lido, preenchendo o anexo \ref{sec:resolucao}
com as respostas. O relatório deverá conter ainda a identificação dos membros
do grupo de trabalho, no local respectivo da folha de rosto.

Para gerar o PDF integral do relatório deve-se ainda correr os comando seguintes,
que actualizam a bibliografia (com \Bibtex) e o índice remissivo (com \Makeindex),
\begin{Verbatim}[fontsize=\small]
    $ bibtex cp2324t.aux
    $ makeindex cp2324t.idx
\end{Verbatim}
e recompilar o texto como acima se indicou. (Como já se disse, pode fazê-lo
correndo simplesmente \texttt{make} no \container.)

No anexo \ref{sec:codigo} disponibiliza-se algum código \Haskell\ relativo
aos problemas que são colocados. Esse anexo deverá ser consultado e analisado
à medida que isso for necessário.

Deve ser feito uso da \litp{programação literária} para documentar bem o código que se
desenvolver, em particular fazendo diagramas explicativos do que foi feito e
tal como se explica no anexo \ref{sec:diagramas}.

\begin{alert}
\textbf{Importante:} o grupo deve evitar trabalhar fora deste ficheiro \lhstotex{lhs}
que lhe é fornecido. Se, para efeitos de divisão de trabalho, o decidir fazer,
deve \textbf{regularmente integrar} e validar as soluções que forem sendo
obtidas neste \lhstotex{lhs}, garantindo atempadamente a compatibilidade com este.

Se não o fizer corre o risco de vir a submeter um ficheiro que não corre
no GHCi e/ou apresenta erros na geração do PDF.
\end{alert}

\section{Como exprimir cálculos e diagramas em LaTeX/lhs2TeX} \label{sec:diagramas}

Como primeiro exemplo, estudar o texto fonte (\lhstotex{lhs}) do que está a ler\footnote{
Procure e.g.\ por \texttt{"sec:diagramas"}.} onde se obtém o efeito seguinte:\footnote{Exemplos
tirados de \cite{Ol18}.}
\begin{eqnarray*}
\start
     \ensuremath{\Varid{id}\mathrel{=}\conj{\Varid{f}}{\Varid{g}}}
%
\just\equiv{ universal property }
%
        \ensuremath{\begin{lcbr}\p1\comp \Varid{id}\mathrel{=}\Varid{f}\\\p2\comp \Varid{id}\mathrel{=}\Varid{g}\end{lcbr}}
%
\just\equiv{ identity }
%
        \ensuremath{\begin{lcbr}\p1\mathrel{=}\Varid{f}\\\p2\mathrel{=}\Varid{g}\end{lcbr}}
\qed
\end{eqnarray*}

Os diagramas podem ser produzidos recorrendo à \emph{package} \LaTeX\
\href{https://ctan.org/pkg/xymatrix}{xymatrix}, por exemplo:
\begin{eqnarray*}
\xymatrix@C=2cm{
    \ensuremath{\N_0}
           \ar[d]_-{\ensuremath{\llparenthesis\, \Varid{g}\,\rrparenthesis}}
&
    \ensuremath{\mathrm{1}\mathbin{+}\N_0}
           \ar[d]^{\ensuremath{\Varid{id}\mathbin{+}\llparenthesis\, \Varid{g}\,\rrparenthesis}}
           \ar[l]_-{\ensuremath{\mathsf{in}}}
\\
     \ensuremath{\Conid{B}}
&
     \ensuremath{\mathrm{1}\mathbin{+}\Conid{B}}
           \ar[l]^-{\ensuremath{\Varid{g}}}
}
\end{eqnarray*}

\section{Regra prática para a recursividade mútua em \ensuremath{\N_0}}\label{sec:mr}

Nesta disciplina estudou-se como fazer \pd{programação dinâmica} por cálculo,
recorrendo à lei de recursividade mútua.\footnote{Lei (\ref{eq:fokkinga})
em \cite{Ol18}, página \pageref{eq:fokkinga}.}

Para o caso de funções sobre os números naturais (\ensuremath{\N_0}, com functor \ensuremath{\fun F \;\Conid{X}\mathrel{=}\mathrm{1}\mathbin{+}\Conid{X}}) pode derivar-se da lei que foi estudada uma
	\emph{regra de algibeira}
	\label{pg:regra}
que se pode ensinar a programadores que não tenham estudado
\cp{Cálculo de Programas}. Apresenta-se de seguida essa regra, tomando como
exemplo o cálculo do ciclo-\textsf{for} que implementa a função de Fibonacci,
recordar o sistema:
\begin{hscode}\SaveRestoreHook
\column{B}{@{}>{\hspre}l<{\hspost}@{}}%
\column{E}{@{}>{\hspre}l<{\hspost}@{}}%
\>[B]{}\Varid{fib}\;\mathrm{0}\mathrel{=}\mathrm{1}{}\<[E]%
\\
\>[B]{}\Varid{fib}\;(\Varid{n}\mathbin{+}\mathrm{1})\mathrel{=}\Varid{f}\;\Varid{n}{}\<[E]%
\\[\blanklineskip]%
\>[B]{}\Varid{f}\;\mathrm{0}\mathrel{=}\mathrm{1}{}\<[E]%
\\
\>[B]{}\Varid{f}\;(\Varid{n}\mathbin{+}\mathrm{1})\mathrel{=}\Varid{fib}\;\Varid{n}\mathbin{+}\Varid{f}\;\Varid{n}{}\<[E]%
\ColumnHook
\end{hscode}\resethooks
Obter-se-á de imediato
\begin{hscode}\SaveRestoreHook
\column{B}{@{}>{\hspre}l<{\hspost}@{}}%
\column{4}{@{}>{\hspre}l<{\hspost}@{}}%
\column{E}{@{}>{\hspre}l<{\hspost}@{}}%
\>[B]{}\Varid{fib'}\mathrel{=}\p1\comp \for{\Varid{loop}}\ {\Varid{init}}\;\mathbf{where}{}\<[E]%
\\
\>[B]{}\hsindent{4}{}\<[4]%
\>[4]{}\Varid{loop}\;(\Varid{fib},\Varid{f})\mathrel{=}(\Varid{f},\Varid{fib}\mathbin{+}\Varid{f}){}\<[E]%
\\
\>[B]{}\hsindent{4}{}\<[4]%
\>[4]{}\Varid{init}\mathrel{=}(\mathrm{1},\mathrm{1}){}\<[E]%
\ColumnHook
\end{hscode}\resethooks
usando as regras seguintes:
\begin{itemize}
\item	O corpo do ciclo \ensuremath{\Varid{loop}} terá tantos argumentos quanto o número de funções mutuamente recursivas.
\item	Para as variáveis escolhem-se os próprios nomes das funções, pela ordem
que se achar conveniente.\footnote{Podem obviamente usar-se outros símbolos, mas numa primeira leitura
dá jeito usarem-se tais nomes.}
\item	Para os resultados vão-se buscar as expressões respectivas, retirando a variável \ensuremath{\Varid{n}}.
\item	Em \ensuremath{\Varid{init}} coleccionam-se os resultados dos casos de base das funções, pela mesma ordem.
\end{itemize}
Mais um exemplo, envolvendo polinómios do segundo grau $ax^2 + b x + c$ em \ensuremath{\N_0}.
Seguindo o método estudado nas aulas\footnote{Secção 3.17 de \cite{Ol18} e tópico
\href{https://www4.di.uminho.pt/~jno/media/cp/}{Recursividade mútua} nos vídeos de apoio às aulas teóricas.},
de $f\ x = a x^2 + b x + c$ derivam-se duas funções mutuamente recursivas:
\begin{hscode}\SaveRestoreHook
\column{B}{@{}>{\hspre}l<{\hspost}@{}}%
\column{E}{@{}>{\hspre}l<{\hspost}@{}}%
\>[B]{}\Varid{f}\;\mathrm{0}\mathrel{=}\Varid{c}{}\<[E]%
\\
\>[B]{}\Varid{f}\;(\Varid{n}\mathbin{+}\mathrm{1})\mathrel{=}\Varid{f}\;\Varid{n}\mathbin{+}\Varid{k}\;\Varid{n}{}\<[E]%
\\[\blanklineskip]%
\>[B]{}\Varid{k}\;\mathrm{0}\mathrel{=}\Varid{a}\mathbin{+}\Varid{b}{}\<[E]%
\\
\>[B]{}\Varid{k}\;(\Varid{n}\mathbin{+}\mathrm{1})\mathrel{=}\Varid{k}\;\Varid{n}\mathbin{+}\mathrm{2}\;\Varid{a}{}\<[E]%
\ColumnHook
\end{hscode}\resethooks
Seguindo a regra acima, calcula-se de imediato a seguinte implementação, em Haskell:
\begin{hscode}\SaveRestoreHook
\column{B}{@{}>{\hspre}l<{\hspost}@{}}%
\column{3}{@{}>{\hspre}l<{\hspost}@{}}%
\column{E}{@{}>{\hspre}l<{\hspost}@{}}%
\>[B]{}\Varid{f'}\;\Varid{a}\;\Varid{b}\;\Varid{c}\mathrel{=}\p1\comp \for{\Varid{loop}}\ {\Varid{init}}\;\mathbf{where}{}\<[E]%
\\
\>[B]{}\hsindent{3}{}\<[3]%
\>[3]{}\Varid{loop}\;(\Varid{f},\Varid{k})\mathrel{=}(\Varid{f}\mathbin{+}\Varid{k},\Varid{k}\mathbin{+}\mathrm{2}\mathbin{*}\Varid{a}){}\<[E]%
\\
\>[B]{}\hsindent{3}{}\<[3]%
\>[3]{}\Varid{init}\mathrel{=}(\Varid{c},\Varid{a}\mathbin{+}\Varid{b}){}\<[E]%
\ColumnHook
\end{hscode}\resethooks

\section{Código fornecido}\label{sec:codigo}

\subsection*{Problema 1}
Tipos básicos:
\begin{hscode}\SaveRestoreHook
\column{B}{@{}>{\hspre}l<{\hspost}@{}}%
\column{E}{@{}>{\hspre}l<{\hspost}@{}}%
\>[B]{}\mathbf{type}\;\Conid{Votes}\mathrel{=}\mathbb{Z}{}\<[E]%
\\
\>[B]{}\mathbf{type}\;\Conid{Deputies}\mathrel{=}\mathbb{Z}{}\<[E]%
\ColumnHook
\end{hscode}\resethooks
Dados:
\begin{hscode}\SaveRestoreHook
\column{B}{@{}>{\hspre}l<{\hspost}@{}}%
\column{E}{@{}>{\hspre}l<{\hspost}@{}}%
\>[B]{}\Varid{db}\mathbin{::}[\mskip1.5mu (\Conid{Party},(\Conid{Votes},\Conid{Deputies}))\mskip1.5mu]{}\<[E]%
\\
\>[B]{}\Varid{db}\mathrel{=}\map \;\Varid{f}\;\Varid{vote}\;\mathbf{where}\;\Varid{f}\;(\Varid{a},\Varid{b})\mathrel{=}(\Varid{a},(\Varid{b},\mathrm{0})){}\<[E]%
\\[\blanklineskip]%
\>[B]{}\Varid{vote}\mathrel{=}[\mskip1.5mu (\Conid{A},\mathrm{12000}),(\Conid{B},\mathrm{7500}),(\Conid{C},\mathrm{4500}),(\Conid{D},\mathrm{3000})\mskip1.5mu]{}\<[E]%
\ColumnHook
\end{hscode}\resethooks
Apuramento:
\begin{hscode}\SaveRestoreHook
\column{B}{@{}>{\hspre}l<{\hspost}@{}}%
\column{E}{@{}>{\hspre}l<{\hspost}@{}}%
\>[B]{}\Varid{final}\mathrel{=}\map \;(\Varid{id}\times\p2)\comp \Varid{last}{}\<[E]%
\\
\>[B]{}\Varid{total}\mathrel{=}\Varid{sum}\;(\map \;\p2\;\Varid{vote}){}\<[E]%
\\
\>[B]{}\Varid{wasted}\mathrel{=}\Varid{waste}\;\Varid{history}{}\<[E]%
\ColumnHook
\end{hscode}\resethooks

\subsection*{Problema 3}
Definição da série de Catalan usando factoriais (\ref{eq:cat}):
\begin{hscode}\SaveRestoreHook
\column{B}{@{}>{\hspre}l<{\hspost}@{}}%
\column{E}{@{}>{\hspre}l<{\hspost}@{}}%
\>[B]{}\Varid{catdef}\;\Varid{n}\mathrel{=}{(\mathrm{2}\mathbin{*}\Varid{n})!}\div ({(\Varid{n}\mathbin{+}\mathrm{1})!}\mathbin{*}{\Varid{n}!}){}\<[E]%
\ColumnHook
\end{hscode}\resethooks
Oráculo para inspecção dos primeiros 26 números de Catalan\footnote{Fonte:
\catalan{Wikipedia}.}:
\begin{hscode}\SaveRestoreHook
\column{B}{@{}>{\hspre}l<{\hspost}@{}}%
\column{5}{@{}>{\hspre}l<{\hspost}@{}}%
\column{E}{@{}>{\hspre}l<{\hspost}@{}}%
\>[B]{}\Varid{oracle}\mathrel{=}[\mskip1.5mu {}\<[E]%
\\
\>[B]{}\hsindent{5}{}\<[5]%
\>[5]{}\mathrm{1},\mathrm{1},\mathrm{2},\mathrm{5},\mathrm{14},\mathrm{42},\mathrm{132},\mathrm{429},\mathrm{1430},\mathrm{4862},\mathrm{16796},\mathrm{58786},\mathrm{208012},\mathrm{742900},\mathrm{2674440},\mathrm{9694845},{}\<[E]%
\\
\>[B]{}\hsindent{5}{}\<[5]%
\>[5]{}\mathrm{35357670},\mathrm{129644790},\mathrm{477638700},\mathrm{1767263190},\mathrm{6564120420},\mathrm{24466267020},{}\<[E]%
\\
\>[B]{}\hsindent{5}{}\<[5]%
\>[5]{}\mathrm{91482563640},\mathrm{343059613650},\mathrm{1289904147324},\mathrm{4861946401452}{}\<[E]%
\\
\>[B]{}\hsindent{5}{}\<[5]%
\>[5]{}\mskip1.5mu]{}\<[E]%
\ColumnHook
\end{hscode}\resethooks


%----------------- Soluções dos alunos -----------------------------------------%

\section{Soluções dos alunos}\label{sec:resolucao}
Os grupos devem colocar neste anexo as suas soluções para os exercícios
propostos, de acordo com o ``layout'' que se fornece.
Não podem ser alterados os nomes ou tipos das funções dadas, mas pode ser adicionado
texto, diagramas e/ou outras funções auxiliares que sejam necessárias.

\begin{alert}
\textbf{Importante}: Não pode ser alterado o texto deste ficheiro fora deste anexo.
\end{alert}

\subsection*{Problema 1}
Ao analisar o problema, percebemos que a resolucao do mesmo dependia do tipo de informação contida no history. Para isso começámos por definir o \textbf{step} e posteriormente o \textbf{waste}.

\begin{hscode}\SaveRestoreHook
\column{B}{@{}>{\hspre}l<{\hspost}@{}}%
\column{9}{@{}>{\hspre}l<{\hspost}@{}}%
\column{11}{@{}>{\hspre}l<{\hspost}@{}}%
\column{13}{@{}>{\hspre}l<{\hspost}@{}}%
\column{E}{@{}>{\hspre}l<{\hspost}@{}}%
\>[B]{}\Varid{step}\;[\mskip1.5mu \mskip1.5mu]\mathrel{=}[\mskip1.5mu \mskip1.5mu]{}\<[E]%
\\
\>[B]{}\Varid{step}\;\Varid{l}\mathrel{=}\Varid{aux}\;\Varid{maxPair}\;\Varid{l}{}\<[E]%
\\
\>[B]{}\hsindent{9}{}\<[9]%
\>[9]{}\mathbf{where}{}\<[E]%
\\
\>[9]{}\hsindent{2}{}\<[11]%
\>[11]{}\Varid{maxPair}\mathrel{=}\Varid{maximumBy}\;(\Varid{comparing}\;(\p1\comp \p2))\;\Varid{l}{}\<[E]%
\\
\>[9]{}\hsindent{2}{}\<[11]%
\>[11]{}\Varid{aux}\;\anonymous \;[\mskip1.5mu \mskip1.5mu]\mathrel{=}[\mskip1.5mu \mskip1.5mu]{}\<[E]%
\\
\>[9]{}\hsindent{2}{}\<[11]%
\>[11]{}\Varid{aux}\;(\Varid{maxP},(\Varid{maxV},\Varid{maxD}))\;((\Varid{p},(\Varid{v},\Varid{d}))\mathbin{:}\Varid{rest}){}\<[E]%
\\
\>[11]{}\hsindent{2}{}\<[13]%
\>[13]{}\mid \Varid{maxP}\equiv \Varid{p}\mathrel{\wedge}\Varid{maxD}\equiv \mathrm{0}\mathrel{=}(\Varid{p},(\Varid{v}\mathbin{\Varid{`div`}}\mathrm{2},\succ \;\Varid{d}))\mathbin{:}\Varid{rest}{}\<[E]%
\\
\>[11]{}\hsindent{2}{}\<[13]%
\>[13]{}\mid \Varid{maxP}\equiv \Varid{p}\mathrel{=}(\Varid{p},((\Varid{v}\mathbin{*}\succ \;\Varid{d})\mathbin{\Varid{`div`}}(\Varid{d}\mathbin{+}\mathrm{2}),\succ \;\Varid{d}))\mathbin{:}\Varid{rest}{}\<[E]%
\\
\>[11]{}\hsindent{2}{}\<[13]%
\>[13]{}\mid \Varid{otherwise}\mathrel{=}(\Varid{p},(\Varid{v},\Varid{d}))\mathbin{:}\Varid{aux}\;\Varid{maxPair}\;\Varid{rest}{}\<[E]%
\ColumnHook
\end{hscode}\resethooks

A cada iteração calculamos o partido com o maior número de votos e guardamos a informação em \textbf{maxPair}.
Se tiver 0 deputados, para obter os "novos" votos, dividimos os votos totais desse partido por 2 e de seguida adicionamos um deputado. 
Se tiver mais que 0 deputados, os votos irão ser a divisão dos votos totais desse partido pelo seu número de deputados mais 2, de seguida aumentamos o número de deputados.
Por fim, se não for o partido com mais votos, mantemos os votos e os deputados inalterados.

\vspace{1em}\vspace{1em}

O \textbf{history} é a aplicação da função \textbf{for} \textbf{step} \textbf{db} em \textbf{i} vezes, que origina uma lista de listas possuindo a informação referente a cada patido (votos, deputados).


\begin{align*}
    0 & \quad [(A,(12000,0)),(B,(7500,0)),(C,(4500,0)),(D,(3000,0))] \\
    1 & \quad [(A,(6000,1)),(B,(7500,0)),(C,(4500,0)),(D,(3000,0))] \\
    2 & \quad [(A,(6000,1)),(B,(3750,1)),(C,(4500,0)),(D,(3000,0))] \\
    3 & \quad [(A,(4000,2)),(B,(3750,1)),(C,(4500,0)),(D,(3000,0))] \\
    4 & \quad [(A,(4000,2)),(B,(3750,1)),(C,(2250,1)),(D,(3000,0))] \\
    5 & \quad [(A,(3000,3)),(B,(3750,1)),(C,(2250,1)),(D,(3000,0))] \\
    6 & \quad [(A,(3000,3)),(B,(2500,2)),(C,(2250,1)),(D,(3000,0))] \\
    7 & \quad [(A,(3000,3)),(B,(2500,2)),(C,(2250,1)),(D,(1500,1))]
\end{align*}

Já o nosso \textbf{waste} soma todos os votos da última lista do \textbf{history}, que contém os votos desperdiçados. 

\begin{hscode}\SaveRestoreHook
\column{B}{@{}>{\hspre}l<{\hspost}@{}}%
\column{E}{@{}>{\hspre}l<{\hspost}@{}}%
\>[B]{}\Varid{waste}\mathrel{=}\Varid{sum}\comp \map \;(\p1\comp \p2)\comp \Varid{last}{}\<[E]%
\ColumnHook
\end{hscode}\resethooks

\subsection*{Problema 2}
Para a descoberta dos genes \textbf{f} e \textbf{g} referentes ao hilomorfismo \textbf{mergek}, elaboramos o seguinte diagrama:

\begin{eqnarray*}         
\xymatrix@C=3cm{
    (A^{*})^{*}
           \ar[r]^-{\mathsf{divide}}
           \ar[d]_-{mergeK}
&
    1 + A \ensuremath{\times} (A^{*})^{*}
           \ar[d]^-{id + id \ensuremath{\times} mergeK}
\\
    A^{*}
&
    1 + A \ensuremath{\times} A^{*}
           \ar[l]^-{\mathsf{conquer = [nil, cons]}}
}
\end{eqnarray*}

Genes de \ensuremath{\Varid{mergek}}:
\begin{hscode}\SaveRestoreHook
\column{B}{@{}>{\hspre}l<{\hspost}@{}}%
\column{5}{@{}>{\hspre}l<{\hspost}@{}}%
\column{9}{@{}>{\hspre}l<{\hspost}@{}}%
\column{25}{@{}>{\hspre}l<{\hspost}@{}}%
\column{E}{@{}>{\hspre}l<{\hspost}@{}}%
\>[B]{}\Varid{f}\mathrel{=}\Varid{inList}{}\<[E]%
\\[\blanklineskip]%
\>[B]{}\Varid{g}\;[\mskip1.5mu \mskip1.5mu]\mathrel{=}i_1\;(){}\<[E]%
\\
\>[B]{}\Varid{g}\;\Varid{l}\mathrel{=}\mathbf{if}\;\Varid{filter}\;(\not\equiv [\mskip1.5mu \mskip1.5mu])\;\Varid{l}\equiv [\mskip1.5mu \mskip1.5mu]{}\<[E]%
\\
\>[B]{}\hsindent{5}{}\<[5]%
\>[5]{}\mathbf{then}\;i_1\;(){}\<[E]%
\\
\>[B]{}\hsindent{5}{}\<[5]%
\>[5]{}\mathbf{else}\;i_2\;(\Varid{m},\Varid{l'})\;\mathbf{where}{}\<[E]%
\\
\>[5]{}\hsindent{4}{}\<[9]%
\>[9]{}\Varid{m}\mathrel{=}\Varid{minimum}\;(\map \;\Varid{head}\;\Varid{x}){}\<[E]%
\\
\>[5]{}\hsindent{4}{}\<[9]%
\>[9]{}\Varid{l'}\mathrel{=}\Varid{aux}\;\Varid{m}\;\Varid{x}{}\<[E]%
\\
\>[5]{}\hsindent{4}{}\<[9]%
\>[9]{}\Varid{aux}\;\anonymous \;[\mskip1.5mu \mskip1.5mu]\mathrel{=}[\mskip1.5mu \mskip1.5mu]{}\<[E]%
\\
\>[5]{}\hsindent{4}{}\<[9]%
\>[9]{}\Varid{aux}\;\Varid{m}\;(\Varid{h}\mathbin{:}\Varid{t})\mathrel{=}\mathbf{if}\;\Varid{m}\equiv \Varid{head}\;\Varid{h}{}\<[E]%
\\
\>[9]{}\hsindent{16}{}\<[25]%
\>[25]{}\mathbf{then}\;\Varid{tail}\;\Varid{h}\mathbin{:}\Varid{t}{}\<[E]%
\\
\>[9]{}\hsindent{16}{}\<[25]%
\>[25]{}\mathbf{else}\;\Varid{h}\mathbin{:}\Varid{aux}\;\Varid{m}\;\Varid{t}{}\<[E]%
\\
\>[5]{}\hsindent{4}{}\<[9]%
\>[9]{}\Varid{x}\mathrel{=}\Varid{filter}\;(\not\equiv [\mskip1.5mu \mskip1.5mu])\;\Varid{l}{}\<[E]%
\ColumnHook
\end{hscode}\resethooks
Na nossa resolução o "núcleo" do algoritmo é realizado em grande parte pelo anamorfismo, ficando como um catamorfismo que é o \textbf{inList}.


\noindent Extensão de \ensuremath{\Varid{mSort}}:

Utilizamos a função \textbf{chunksOf} para dividir a lista em k partes, assegurando que a divisão só ocorre se o comprimento da lista for superior a k. Desta forma, evitamos que o algoritmo entre em ciclo infinito. Posteriormente, utilizamos a função \textbf{mergek} para juntar as partes ordenadas.
\begin{hscode}\SaveRestoreHook
\column{B}{@{}>{\hspre}l<{\hspost}@{}}%
\column{5}{@{}>{\hspre}l<{\hspost}@{}}%
\column{17}{@{}>{\hspre}l<{\hspost}@{}}%
\column{E}{@{}>{\hspre}l<{\hspost}@{}}%
\>[B]{}\Varid{mSortk}\;\Varid{k}\;[\mskip1.5mu \mskip1.5mu]\mathrel{=}[\mskip1.5mu \mskip1.5mu]{}\<[E]%
\\
\>[B]{}\Varid{mSortk}\;\Varid{k}\;\Varid{l}{}\<[E]%
\\
\>[B]{}\hsindent{5}{}\<[5]%
\>[5]{}\mid \length \;\Varid{l}\leq \mathrm{1}\mathrel{=}\Varid{l}{}\<[E]%
\\
\>[B]{}\hsindent{5}{}\<[5]%
\>[5]{}\mid \Varid{otherwise}\mathrel{=}\mathbf{let}\;\Varid{chunks}\mathrel{=}\Varid{chunksOf}\;(\mathbf{if}\;\length \;\Varid{l}\leq \Varid{k}\;\mathbf{then}\;\mathrm{1}\;\mathbf{else}\;\Varid{k})\;\Varid{l}{}\<[E]%
\\
\>[5]{}\hsindent{12}{}\<[17]%
\>[17]{}\mathbf{in}\;\Varid{mergek}\;(\map \;(\Varid{mSortk}\;\Varid{k})\;\Varid{chunks}){}\<[E]%
\ColumnHook
\end{hscode}\resethooks
Com uma abordagem que divide a lista em k partes, é possível reduzir significativamente o número de comparações e operações necessárias para ordenar a lista, tornando o algoritmo mais eficiente. Este método beneficia do paralelismo, uma vez que permite dividir a lista em k partes e ordená-las em simultâneo.

Cada parte pode ser ordenada de forma independente e, posteriormente, combinada para formar a lista ordenada final. Isto não só distribui a carga de trabalho, como também reduz o tempo total de execução. Esta abordagem é escalável, podendo ser ajustada para diferentes tamanhos de listas.

\subsection*{Problema 3}
Para a simplificação do algoritmo de Catalan sem recurso ao cálculo dos factoriais
é necessário reescrever a fórmula. A simplificação é a seguinte descrita:

\begin{eqnarray}
C_n = \frac{(2n)!}{(n+1)! (n!) }
\label{eq:cat}
\end{eqnarray}
\begin{eqnarray}
    C_n = \frac{(2n)(2n-1)!}{(n+1)n!*n(n-1)! }
    \label{eq:cat}
\end{eqnarray}
\begin{eqnarray}
    C_n = \frac{2(2n-1)!}{(n+1)n!*(n-1)! }
    \label{eq:cat}
\end{eqnarray}
\begin{eqnarray}
    C_n = \frac{2(2n-1)(2n-2)!}{(n+1)n!*(n-1)(n-2)! }
    \label{eq:cat}
\end{eqnarray}
\hspace{2cm} ...

A continuação da simplificação matemática mostraria que era possível
obter o número de Catalan atual, usando o número de Catalan anterior.

Pelo link da Wikipédia disponibilizada pela equipa docente sabemos que:
\begin{eqnarray}
    C_0 = 1
    \label{eq:cat}
\end{eqnarray}
\begin{eqnarray}
    C_n = \frac{2(2n-1)}{n+1 }*C_{n-1}
    \label{eq:cat}
\end{eqnarray}
Que iremos simplificar para 
\begin{eqnarray}
    C_n = \frac{4n-2}{n+1 }*C_{n-1}
    \label{eq:cat}
\end{eqnarray}
Para reduzir o número de operações.

Sabendo como se escreve 
\begin{eqnarray}C_n\label{eq:cat}\end{eqnarray} 
através de 
\begin{eqnarray}C_{n-1}\label{eq:cat}\end{eqnarray} 
é possível escrever a recursividade mútua do algoritmo.

O nosso \textbf{inic} será composto por um par (a,b) que será inicializado com (1,1).
O loop é responsável por aplicar a função succ ao primeiro elemento e a executar a chamada recursiva no segundo elemento do \textbf{inic}.
A primeira componente serve para guardar a iteração atual, já a segunda guarda o número de Catalan.
Sendo assim, ficamos com o seguinte algoritmo:

\begin{hscode}\SaveRestoreHook
\column{B}{@{}>{\hspre}l<{\hspost}@{}}%
\column{E}{@{}>{\hspre}l<{\hspost}@{}}%
\>[B]{}\Varid{cat}\mathrel{=}\Varid{prj}\comp \for{\Varid{loop}}\ {\Varid{inic}}{}\<[E]%
\ColumnHook
\end{hscode}\resethooks
onde:
\begin{hscode}\SaveRestoreHook
\column{B}{@{}>{\hspre}l<{\hspost}@{}}%
\column{E}{@{}>{\hspre}l<{\hspost}@{}}%
\>[B]{}\Varid{loop}\;(\Varid{a},\Varid{b})\mathrel{=}(\Varid{a}\mathbin{+}\mathrm{1},\Varid{b}\mathbin{*}((\mathrm{4}\mathbin{*}\Varid{a})\mathbin{-}\mathrm{2})\mathbin{\Varid{`div`}}(\Varid{a}\mathbin{+}\mathrm{1})){}\<[E]%
\\
\>[B]{}\Varid{inic}\mathrel{=}(\mathrm{1},\mathrm{1}){}\<[E]%
\\
\>[B]{}\Varid{prj}\mathrel{=}\p2{}\<[E]%
\ColumnHook
\end{hscode}\resethooks

\subsection*{Problema 4}

Neste problema, recebemos uma lista de números que representam as áreas dos retângulos do histograma, e queremos encontrar o maior retângulo contido no histograma.

Diagrama para a resolução do problema:

\begin{eqnarray*}         
\xymatrix@C=5cm{
    A^{*}
           \ar[r]^-{\mathsf{m}}
           \ar[d]_-{[(m)]}
&
    1 + A^{*} \ensuremath{\times} A^{*}
           \ar[d]^-{id + id \ensuremath{\times} m}
\\
    (A^{*})^{*}
        \ar@/^/[r]^-{\mathsf{out}}
        \ar[d]_-{([n])}
&
    1 + A^{*} \ensuremath{\times} (A^{*})^{*}
           \ar@/^/[l]^-{\mathsf{in = [nil, cons]}}
           \ar[d]^-{id + id \ensuremath{\times} n}
\\
    A
&
    1 + A^{*} \ensuremath{\times} A
           \ar[l]^-{\mathsf{n}}
}
\end{eqnarray*}

Para o resolver, usamos um hilomorfismo. Primeiramente, o anamorfismo \textbf{[( m )]} gera uma lista de listas retira constantemente a cabeça da lista anterior. Por exemplo, se aplicarmos \textbf{[( m )]} à lista [1,2,3] obtemos a lista de listas [[1,2,3], [2,3], [3]]. \\
Já no catamorfismo, para cada uma destas sublistas, calculamos o maior retângulo a partir da cabeça da lista. No exemplo passado, seria calculado o maior retângulo a começar na barra 1, o maior começado barra 2 e a começar na barra 3. A nossa função \textbf{lR} faz esse cálculo. \\
Após aplicar a função \textbf{map lR} ao resultado do anamorfismo, precisamos de determinar qual é o maior valor.

\begin{hscode}\SaveRestoreHook
\column{B}{@{}>{\hspre}l<{\hspost}@{}}%
\column{5}{@{}>{\hspre}l<{\hspost}@{}}%
\column{17}{@{}>{\hspre}l<{\hspost}@{}}%
\column{E}{@{}>{\hspre}l<{\hspost}@{}}%
\>[B]{}\Varid{m}\;[\mskip1.5mu \mskip1.5mu]\mathrel{=}i_1\;(){}\<[E]%
\\
\>[B]{}\Varid{m}\;\Varid{x}\mathrel{=}i_2\;(\Varid{x},\Varid{tail}\;\Varid{x}){}\<[E]%
\\[\blanklineskip]%
\>[B]{}\Varid{lR}\;[\mskip1.5mu \mskip1.5mu]\mathrel{=}\mathrm{0}{}\<[E]%
\\
\>[B]{}\Varid{lR}\;[\mskip1.5mu \Varid{x}\mskip1.5mu]\mathrel{=}\Varid{x}{}\<[E]%
\\
\>[B]{}\Varid{lR}\;(\Varid{x}\mathbin{:}\Varid{y}\mathbin{:}\Varid{xs}){}\<[E]%
\\
\>[B]{}\hsindent{5}{}\<[5]%
\>[5]{}\mid \Varid{x}\mathbin{>}\Varid{y}{}\<[17]%
\>[17]{}\mathrel{=}\Varid{x}{}\<[E]%
\\
\>[B]{}\hsindent{5}{}\<[5]%
\>[5]{}\mid \Varid{x}\leq \Varid{y}{}\<[17]%
\>[17]{}\mathrel{=}\Varid{x}\mathbin{+}\Varid{lR}\;(\Varid{x}\mathbin{:}\Varid{xs}){}\<[E]%
\\[\blanklineskip]%
\>[B]{}\Varid{gmax}\mathrel{=}\alt{\underline{\mathrm{0}}}{\Varid{umax}}{}\<[E]%
\\[\blanklineskip]%
\>[B]{}\Varid{n}\mathrel{=}\Varid{gmax}\comp \Varid{baseList}\;\Varid{lR}\;\Varid{id}{}\<[E]%
\\[\blanklineskip]%
\>[B]{}\Varid{lrh}\mathrel{=}\hyloList{\Varid{n}}{\Varid{m}}{}\<[E]%
\ColumnHook
\end{hscode}\resethooks
Para concluir, o nosso \textbf{gmax} é o gene do catamorfismo \textbf{maximum} e usamos a lei de absorção-cata para escrever \textbf{maximum . (map lR)} como um catamorfismo de gene \textbf{gmax . baseList lR id} e assim obtemos a solução final.

%----------------- Índice remissivo (exige makeindex) -------------------------%

\printindex

%----------------- Bibliografia (exige bibtex) --------------------------------%

\bibliographystyle{plain}
\bibliography{cp2324t}

%----------------- Fim do documento -------------------------------------------%
\end{document}