-
Notifications
You must be signed in to change notification settings - Fork 0
/
cp1819t.tex
2228 lines (2099 loc) · 108 KB
/
cp1819t.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
\documentclass[a4paper]{article}
\usepackage[a4paper,left=3cm,right=2cm,top=2.5cm,bottom=2.5cm]{geometry}
\usepackage{palatino}
\usepackage[colorlinks=true,linkcolor=blue,citecolor=blue]{hyperref}
\usepackage{graphicx}
\usepackage{cp1819t}
\usepackage{subcaption}
\usepackage{adjustbox}
\usepackage{color}
%================= local x=====================================================%
\def\getGif#1{\includegraphics[width=0.3\textwidth]{cp1819t_media/#1.png}}
\let\uk=\emph
\def\aspas#1{``#1"}
%================= 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
%
\def\ana#1{\mathopen{[\!(}#1\mathclose{)\!]}}
%---------------------------------------------------------------------------
\title{
Cálculo de Programas
\\
Trabalho Prático
\\
MiEI+LCC --- 2018/19
}
\author{
\dium
\\
Universidade do Minho
}
\date\mydate
\makeindex
\newcommand{\rn}[1]{\textcolor{red}{#1}}
\begin{document}
\maketitle
\begin{center}\large
\begin{tabular}{ll}
\textbf{Grupo} nr. & 22
\\\hline
a84003 & Beatriz Rocha
\\
a85308 & Filipe Guimarães
\\
a84073 & Gonçalo Ferreira
\end{tabular}
\end{center}
\section{Preâmbulo}
A disciplina de \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 dois cursos que têm
esta disciplina, restringe-se a aplicação deste método à programação
funcional em \Haskell. 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, validá-los, e a produzir textos técnico-científicos de
qualidade.
\section{Documentação} Para cumprir de forma integrada os objectivos
enunciados acima 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 código fonte e a documentação de um
programa deverão estar no mesmo ficheiro.
O ficheiro \texttt{cp1819t.pdf} que está a ler é já um exemplo de \litp{programação
literária}: foi gerado a partir do texto fonte \texttt{cp1819t.lhs}\footnote{O
suffixo `lhs' quer dizer \emph{\lhaskell{literate Haskell}}.} que encontrará
no \MaterialPedagogico\ desta disciplina descompactando o ficheiro \texttt{cp1819t.zip}
e executando
\begin{Verbatim}[fontsize=\small]
$ lhs2TeX cp1819t.lhs > cp1819t.tex
$ pdflatex cp1819t
\end{Verbatim}
em que \href{https://hackage.haskell.org/package/lhs2tex}{\texttt\LhsToTeX} é
um pre-processador que faz ``pretty printing''
de código Haskell em \Latex\ e que deve desde já instalar executando
\begin{Verbatim}[fontsize=\small]
$ cabal install lhs2tex
\end{Verbatim}
Por outro lado, o mesmo ficheiro \texttt{cp1819t.lhs} é executável e contém
o ``kit'' básico, escrito em \Haskell, para realizar o trabalho. Basta executar
\begin{Verbatim}[fontsize=\small]
$ ghci cp1819t.lhs
\end{Verbatim}
\noindent Abra o ficheiro \texttt{cp1819t.lhs} no seu editor de texto preferido
e verifique que assim é: todo o texto que se encontra dentro do ambiente
\begin{quote}\small\tt
\text{\tt \char92{}begin\char123{}code\char125{}}
\\ ... \\
\text{\tt \char92{}end\char123{}code\char125{}}
\end{quote}
vai ser seleccionado pelo \GHCi\ para ser executado.
\section{Como realizar o trabalho}
Este trabalho teórico-prático deve ser realizado por grupos de três 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
de trabalho por forma a poderem responder às questões que serão colocadas
na \emph{defesa oral} do relatório.
Em que consiste, então, o \emph{relatório} a que se refere o parágrafo anterior?
É 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 cp1819t.aux
$ makeindex cp1819t.idx
\end{Verbatim}
e recompilar o texto como acima se indicou. Dever-se-á ainda instalar o utilitário
\QuickCheck,
que ajuda a validar programas em \Haskell\ e a biblioteca \gloss{Gloss} para
geração de gráficos 2D:
\begin{Verbatim}[fontsize=\small]
$ cabal install QuickCheck gloss
\end{Verbatim}
Para testar uma propriedade \QuickCheck~\ensuremath{\Varid{prop}}, basta invocá-la com o comando:
\begin{tabbing}\tt
~~~~~\char62{}~quickCheck~prop\\
\tt ~~~~~\char43{}\char43{}\char43{}~OK\char44{}~passed~100~tests\char46{}
\end{tabbing}
Qualquer programador tem, na vida real, de ler e analisar (muito!) código
escrito por outros. No anexo \ref{sec:codigo} disponibiliza-se algum
código \Haskell\ relativo aos problemas que se seguem. Esse anexo deverá
ser consultado e analisado à medida que isso for necessário.
\Problema
Um compilador é um programa que traduz uma linguagem dita de
\emph{alto nível} numa linguagem (dita de \emph{baixo nível}) que
seja executável por uma máquina.
Por exemplo, o \gcc{GCC} compila C/C++ em código objecto que
corre numa variedade de arquitecturas.
Compiladores são normalmente programas complexos.
Constam essencialmente de duas partes:
o \emph{analisador sintático} que lê o texto de entrada
(o programa \emph{fonte} a compilar) e cria uma sua representação
interna, estruturada em árvore;
e o \emph{gerador de código} que converte essa representação interna
em código executável.
Note-se que tal representação intermédia pode ser usada para outros fins,
por exemplo,
para gerar uma listagem de qualidade (\uk{pretty print}) do programa fonte.
O projecto de compiladores é um assunto complexo que
será assunto de outras disciplinas.
Neste trabalho pretende-se apenas fazer uma introdução ao assunto,
mostrando como tais programas se podem construir funcionalmente à custa de
cata/ana/hilo-morfismos da linguagem em causa.
Para cumprirmos o nosso objectivo, a linguagem desta questão terá que ser, naturalmente,
muito simples: escolheu-se a das expressões aritméticas com inteiros,
\eg\ \( 1 + 2 \), \( 3 * (4 + 5) \) etc.
Como representação interna adopta-se o seguinte tipo polinomial, igualmente simples:
%
\begin{hscode}\SaveRestoreHook
\column{B}{@{}>{\hspre}l<{\hspost}@{}}%
\column{E}{@{}>{\hspre}l<{\hspost}@{}}%
\>[B]{}\mathbf{data}\;\Conid{Expr}\mathrel{=}\Conid{Num}\;\Conid{Int}\mid \Conid{Bop}\;\Conid{Expr}\;\Conid{Op}\;\Conid{Expr}{}\<[E]%
\\
\>[B]{}\mathbf{data}\;\Conid{Op}\mathrel{=}\Conid{Op}\;\Conid{String}{}\<[E]%
\ColumnHook
\end{hscode}\resethooks
\begin{enumerate}
\item
Escreva as definições dos \{cata, ana e hilo\}-morfismos deste tipo de dados
segundo o método ensinado nesta disciplina (recorde módulos como \eg\ \ensuremath{\fun{BTree} } etc).
\item
Como aplicação do módulo desenvolvido no ponto 1,
defina como \{cata, ana ou hilo\}-morfismo a função seguinte:
\begin{itemize}
\item \ensuremath{\Varid{calcula}\mathbin{::}\Conid{Expr}\to \Conid{Int}} que calcula o valor
de uma expressão;
\begin{propriedade}
O valor zero é um elemento neutro da adição.
\begin{hscode}\SaveRestoreHook
\column{B}{@{}>{\hspre}l<{\hspost}@{}}%
\column{13}{@{}>{\hspre}l<{\hspost}@{}}%
\column{E}{@{}>{\hspre}l<{\hspost}@{}}%
\>[B]{}\Varid{prop\char95 neutro1}\mathbin{::}\Conid{Expr}\to \Conid{Bool}{}\<[E]%
\\
\>[B]{}\Varid{prop\char95 neutro1}\mathrel{=}\Varid{calcula}\comp \Varid{addZero}\equiv\Varid{calcula}\;\mathbf{where}{}\<[E]%
\\
\>[B]{}\hsindent{13}{}\<[13]%
\>[13]{}\Varid{addZero}\;\Varid{e}\mathrel{=}\Conid{Bop}\;(\Conid{Num}\;\mathrm{0})\;(\Conid{Op}\;\text{\tt \char34 +\char34})\;\Varid{e}{}\<[E]%
\\
\>[B]{}\Varid{prop\char95 neutro2}\mathbin{::}\Conid{Expr}\to \Conid{Bool}{}\<[E]%
\\
\>[B]{}\Varid{prop\char95 neutro2}\mathrel{=}\Varid{calcula}\comp \Varid{addZero}\equiv\Varid{calcula}\;\mathbf{where}{}\<[E]%
\\
\>[B]{}\hsindent{13}{}\<[13]%
\>[13]{}\Varid{addZero}\;\Varid{e}\mathrel{=}\Conid{Bop}\;\Varid{e}\;(\Conid{Op}\;\text{\tt \char34 +\char34})\;(\Conid{Num}\;\mathrm{0}){}\<[E]%
\ColumnHook
\end{hscode}\resethooks
\end{propriedade}
\begin{propriedade}
As operações de soma e multiplicação são comutativas.
\begin{hscode}\SaveRestoreHook
\column{B}{@{}>{\hspre}l<{\hspost}@{}}%
\column{13}{@{}>{\hspre}l<{\hspost}@{}}%
\column{E}{@{}>{\hspre}l<{\hspost}@{}}%
\>[B]{}\Varid{prop\char95 comuta}\mathrel{=}\Varid{calcula}\comp \Varid{mirror}\equiv\Varid{calcula}\;\mathbf{where}{}\<[E]%
\\
\>[B]{}\hsindent{13}{}\<[13]%
\>[13]{}\Varid{mirror}\mathrel{=}\Varid{cataExpr}\;\alt{\Conid{Num}}{\Varid{g2}}{}\<[E]%
\\
\>[B]{}\hsindent{13}{}\<[13]%
\>[13]{}\Varid{g2}\mathrel{=}\uncurry{\uncurry{\Conid{Bop}}}\comp (\Varid{swap}\times\Varid{id})\comp \Varid{assocl}\comp (\Varid{id}\times\Varid{swap}){}\<[E]%
\ColumnHook
\end{hscode}\resethooks
\end{propriedade}
\end{itemize}
\item
Defina como \{cata, ana ou hilo\}-morfismos as funções
\begin{itemize}
\item \ensuremath{\Varid{compile}\mathbin{::}\Conid{String}\to \Conid{Codigo}} - trata-se do compilador propriamente
dito. Deverá ser gerado código posfixo para uma máquina elementar
de \pda{stack}. O tipo \ensuremath{\Conid{Codigo}} pode ser definido à escolha.
Dão-se a seguir exemplos de comportamentos aceitáveis para esta
função:
\begin{tabbing}\tt
~Tp4\char62{}~compile~\char34{}2\char43{}4\char34{}\\
\tt ~\char91{}\char34{}PUSH~2\char34{}\char44{}~\char34{}PUSH~4\char34{}\char44{}~\char34{}ADD\char34{}\char93{}\\
\tt ~Tp4\char62{}~compile~\char34{}3\char42{}\char40{}2\char43{}4\char41{}\char34{}\\
\tt ~\char91{}\char34{}PUSH~3\char34{}\char44{}~\char34{}PUSH~2\char34{}\char44{}~\char34{}PUSH~4\char34{}\char44{}~\char34{}ADD\char34{}\char44{}~\char34{}MUL\char34{}\char93{}\\
\tt ~Tp4\char62{}~compile~\char34{}\char40{}3\char42{}2\char41{}\char43{}4\char34{}\\
\tt ~\char91{}\char34{}PUSH~3\char34{}\char44{}~\char34{}PUSH~2\char34{}\char44{}~\char34{}MUL\char34{}\char44{}~\char34{}PUSH~4\char34{}\char44{}~\char34{}ADD\char34{}\char93{}\\
\tt ~Tp4\char62{}
\end{tabbing}
\item \ensuremath{\Varid{show'}\mathbin{::}\Conid{Expr}\to \Conid{String}} - gera a representação textual
de uma \ensuremath{\Conid{Expr}} pode encarar-se como o \uk{pretty printer}
associado ao nosso compilador
\begin{propriedade}
Em anexo, é fornecido o código da função \ensuremath{\Varid{readExp}}, que é ``inversa" da função \ensuremath{\Varid{show'}},
tal como a propriedade seguinte descreve:
\begin{hscode}\SaveRestoreHook
\column{B}{@{}>{\hspre}l<{\hspost}@{}}%
\column{E}{@{}>{\hspre}l<{\hspost}@{}}%
\>[B]{}\Varid{prop\char95 inv}\mathbin{::}\Conid{Expr}\to \Conid{Bool}{}\<[E]%
\\
\>[B]{}\Varid{prop\char95 inv}\mathrel{=}\p1\comp \Varid{head}\comp \Varid{readExp}\comp \Varid{show'}\equiv\Varid{id}{}\<[E]%
\ColumnHook
\end{hscode}\resethooks
\end{propriedade}
\end{itemize}
%% \item Generalize o tipo |Expr| de forma a admitir operadores
%% unários (\eg\ \(-5\)) e repita os exercícios dos pontos anteriores.
\end{enumerate}
\paragraph{Valorização}
Em anexo é apresentado código \Haskell\ que permite declarar
\ensuremath{\Conid{Expr}} como instância da classe \ensuremath{\Conid{Read}}. Neste contexto,
\ensuremath{\Varid{read}} pode ser vista como o analisador
sintático do nosso minúsculo compilador de expressões aritméticas.
Analise o código apresentado, corra-o e escreva no seu relatório uma explicação
\textbf{breve} do seu funcionamento, que deverá saber defender aquando da
apresentação oral do relatório.
Exprima ainda o analisador sintático \ensuremath{\Varid{readExp}} como um anamorfismo.
\Problema
Pretende-se neste problema definir uma linguagem gráfica \aspas{brinquedo}
a duas dimensões (2D) capaz de especificar e desenhar agregações de
caixas que contêm informação textual.
Vamos designar essa linguagem por \ensuremath{\Conid{L2D}} e vamos defini-la como um tipo
em \Haskell:
\begin{hscode}\SaveRestoreHook
\column{B}{@{}>{\hspre}l<{\hspost}@{}}%
\column{E}{@{}>{\hspre}l<{\hspost}@{}}%
\>[B]{}\mathbf{type}\;\Conid{L2D}\mathrel{=}\Conid{X}\;\Conid{Caixa}\;\Conid{Tipo}{}\<[E]%
\ColumnHook
\end{hscode}\resethooks
onde \ensuremath{\Conid{X}} é a estrutura de dados
\begin{hscode}\SaveRestoreHook
\column{B}{@{}>{\hspre}l<{\hspost}@{}}%
\column{E}{@{}>{\hspre}l<{\hspost}@{}}%
\>[B]{}\mathbf{data}\;\Conid{X}\;\Varid{a}\;\Varid{b}\mathrel{=}\Conid{Unid}\;\Varid{a}\mid \Conid{Comp}\;\Varid{b}\;(\Conid{X}\;\Varid{a}\;\Varid{b})\;(\Conid{X}\;\Varid{a}\;\Varid{b})\;\mathbf{deriving}\;\Conid{Show}{}\<[E]%
\ColumnHook
\end{hscode}\resethooks
e onde:
\begin{hscode}\SaveRestoreHook
\column{B}{@{}>{\hspre}l<{\hspost}@{}}%
\column{E}{@{}>{\hspre}l<{\hspost}@{}}%
\>[B]{}\mathbf{type}\;\Conid{Caixa}\mathrel{=}((\Conid{Int},\Conid{Int}),(\Conid{Texto},\Conid{\Conid{G}.Color})){}\<[E]%
\\
\>[B]{}\mathbf{type}\;\Conid{Texto}\mathrel{=}\Conid{String}{}\<[E]%
\ColumnHook
\end{hscode}\resethooks
Assim, cada caixa de texto é especificada pela sua largura, altura, o seu
texto e a sua côr.\footnote{Pode relacionar \ensuremath{\Conid{Caixa}} com as caixas de texto usadas
nos jornais ou com \uk{frames} da linguagem \Html\ usada na Internet.}
Por exemplo,
\begin{hscode}\SaveRestoreHook
\column{B}{@{}>{\hspre}l<{\hspost}@{}}%
\column{E}{@{}>{\hspre}l<{\hspost}@{}}%
\>[B]{}((\mathrm{200},\mathrm{200}),(\text{\tt \char34 Caixa~azul\char34},\Varid{col\char95 blue})){}\<[E]%
\ColumnHook
\end{hscode}\resethooks
designa a caixa da esquerda da figura \ref{fig:L2D}.
O que a linguagem \ensuremath{\Conid{L2D}} faz é agregar tais caixas tipográficas
umas com as outras segundo padrões especificados por vários
\aspas{tipos}, a saber,
\begin{hscode}\SaveRestoreHook
\column{B}{@{}>{\hspre}l<{\hspost}@{}}%
\column{E}{@{}>{\hspre}l<{\hspost}@{}}%
\>[B]{}\mathbf{data}\;\Conid{Tipo}\mathrel{=}\Conid{V}\mid \Conid{Vd}\mid \Conid{Ve}\mid \Conid{H}\mid \Conid{Ht}\mid \Conid{Hb}{}\<[E]%
\ColumnHook
\end{hscode}\resethooks
com o seguinte significado:
\begin{itemize}
\item[\ensuremath{\Conid{V}}] - agregação vertical alinhada ao centro
\item[\ensuremath{\Conid{Vd}}] - agregação vertical justificada à direita
\item[\ensuremath{\Conid{Ve}}] - agregação vertical justificada à esquerda
\item[\ensuremath{\Conid{H}}] - agregação horizontal alinhada ao centro
\item[\ensuremath{\Conid{Hb}}] - agregação horizontal alinhada pela base
\item[\ensuremath{\Conid{Ht}}] - agregação horizontal alinhada pelo topo
\end{itemize}
Como \ensuremath{\Conid{L2D}} instancia o parâmetro \ensuremath{\Varid{b}} de \ensuremath{\Conid{X}} com
\ensuremath{\Conid{Tipo}}, é fácil de ver que cada \aspas{frase} da linguagem
\ensuremath{\Conid{L2D}} é representada por uma árvore binária em que cada nó
indica qual o tipo de agregação a aplicar às suas duas sub-árvores.
%
Por exemplo, a frase
\begin{hscode}\SaveRestoreHook
\column{B}{@{}>{\hspre}l<{\hspost}@{}}%
\column{15}{@{}>{\hspre}l<{\hspost}@{}}%
\column{E}{@{}>{\hspre}l<{\hspost}@{}}%
\>[B]{}\Varid{ex2}\mathrel{=}\Conid{Comp}\;\Conid{Hb}\;{}\<[15]%
\>[15]{}(\Conid{Unid}\;((\mathrm{100},\mathrm{200}),(\text{\tt \char34 A\char34},\Varid{col\char95 blue})))\;{}\<[E]%
\\
\>[15]{}(\Conid{Unid}\;((\mathrm{50},\mathrm{50}),(\text{\tt \char34 B\char34},\Varid{col\char95 green}))){}\<[E]%
\ColumnHook
\end{hscode}\resethooks
deverá corresponder à imagem da direita da figura \ref{fig:L2D}.
E poder-se-á ir tão longe quando a linguagem o permita. Por exemplo, pense na
estrutura da frase que representa o \uk{layout} da figura \ref{fig:L2D1}.
\begin{figure}
\centering
\begin{picture}(190.00,130.00)(-15,-15)
\put(00.00,0.00){$(0,0)$}
\put(80.00,50.00){$(200,200)$}
\put(20.00,-10.00){
\includegraphics[width=70\unitlength]{cp1819t_media/ex3.png}
}
\end{picture}
%
\includegraphics[width=0.2\textwidth]{cp1819t_media/ex2.png}
%
\caption{Caixa simples e caixa composta.\label{fig:L2D}}
\end{figure}
\begin{figure}
\centering
\includegraphics[width=0.6\textwidth]{cp1819t_media/ex.png}
\caption{\uk{Layout} feito de várias caixas coloridas.\label{fig:L2D1}}
\end{figure}
É importante notar que cada ``caixa'' não dispõe informação relativa
ao seu posicionamento final na figura. De facto, é a posição relativa
que deve ocupar face às restantes caixas que irá determinar a sua
posição final. Este é um dos objectivos deste trabalho:
\emph{calcular o posicionamento absoluto de cada uma das caixas por forma a
respeitar as restrições impostas pelas diversas agregações}. Para isso vamos
considerar um tipo de dados que comporta a informação de todas as
caixas devidamente posicionadas (i.e. com a informação adicional da
origem onde a caixa deve ser colocada).
\begin{hscode}\SaveRestoreHook
\column{B}{@{}>{\hspre}l<{\hspost}@{}}%
\column{E}{@{}>{\hspre}l<{\hspost}@{}}%
\>[B]{}\mathbf{type}\;\Conid{Fig}\mathrel{=}[\mskip1.5mu (\Conid{Origem},\Conid{Caixa})\mskip1.5mu]{}\<[E]%
\\
\>[B]{}\mathbf{type}\;\Conid{Origem}\mathrel{=}(\Conid{Float},\Conid{Float}){}\<[E]%
\ColumnHook
\end{hscode}\resethooks
%
A informação mais relevante deste tipo é a referente à lista de
``caixas posicionadas'' (tipo \ensuremath{(\Conid{Origem},\Conid{Caixa})}). Regista-se aí a origem
da caixa que, com a informação da sua altura e comprimento, permite
definir todos os seus pontos (consideramos as caixas sempre paralelas
aos eixos).
\begin{enumerate}
\item Forneça a definição da função \ensuremath{\Varid{calc\char95 origems}}, que calcula as
coordenadas iniciais das caixas no plano:
\begin{hscode}\SaveRestoreHook
\column{B}{@{}>{\hspre}l<{\hspost}@{}}%
\column{E}{@{}>{\hspre}l<{\hspost}@{}}%
\>[B]{}\Varid{calc\char95 origems}\mathbin{::}(\Conid{L2D},\Conid{Origem})\to \Conid{X}\;(\Conid{Caixa},\Conid{Origem})\;(){}\<[E]%
\ColumnHook
\end{hscode}\resethooks
\item Forneça agora a definição da função \ensuremath{\Varid{agrup\char95 caixas}}, que agrupa
todas as caixas e respectivas origens numa só lista:
\begin{hscode}\SaveRestoreHook
\column{B}{@{}>{\hspre}l<{\hspost}@{}}%
\column{E}{@{}>{\hspre}l<{\hspost}@{}}%
\>[B]{}\Varid{agrup\char95 caixas}\mathbin{::}\Conid{X}\;(\Conid{Caixa},\Conid{Origem})\;()\to \Conid{Fig}{}\<[E]%
\ColumnHook
\end{hscode}\resethooks
\end{enumerate}
Um segundo problema neste projecto é \emph{descobrir como visualizar a
informação gráfica calculada por \ensuremath{\Varid{desenho}}}. A nossa estratégia para
superar o problema baseia-se na biblioteca \gloss{Gloss}, que permite a geração
de gráficos 2D. Para tal disponibiliza-se a função
\begin{hscode}\SaveRestoreHook
\column{B}{@{}>{\hspre}l<{\hspost}@{}}%
\column{20}{@{}>{\hspre}l<{\hspost}@{}}%
\column{E}{@{}>{\hspre}l<{\hspost}@{}}%
\>[B]{}\Varid{crCaixa}\mathbin{::}\Conid{Origem}{}\<[20]%
\>[20]{}\to \Conid{Float}\to \Conid{Float}\to \Conid{String}\to \Conid{\Conid{G}.Color}\to \Conid{\Conid{G}.Picture}{}\<[E]%
\ColumnHook
\end{hscode}\resethooks
que cria um rectângulo com base numa coordenada, um valor para a largura, um valor
para a altura, um texto que irá servir de etiqueta, e a cor pretendida.
Disponibiliza-se também a função
\begin{hscode}\SaveRestoreHook
\column{B}{@{}>{\hspre}l<{\hspost}@{}}%
\column{E}{@{}>{\hspre}l<{\hspost}@{}}%
\>[B]{}\Varid{display}\mathbin{::}\Conid{\Conid{G}.Picture}\to \fun{IO}\;(){}\<[E]%
\ColumnHook
\end{hscode}\resethooks
que dado um valor do tipo \ensuremath{\Varid{\Conid{G}.picture}} abre uma janela com esse valor desenhado. O objectivo
final deste exercício é implementar então uma função
\begin{hscode}\SaveRestoreHook
\column{B}{@{}>{\hspre}l<{\hspost}@{}}%
\column{E}{@{}>{\hspre}l<{\hspost}@{}}%
\>[B]{}\Varid{mostra\char95 caixas}\mathbin{::}(\Conid{L2D},\Conid{Origem})\to \fun{IO}\;(){}\<[E]%
\ColumnHook
\end{hscode}\resethooks
que dada uma frase da linguagem \ensuremath{\Conid{L2D}} e coordenadas iniciais apresenta
o respectivo desenho no ecrã.
%
\textbf{Sugestão}:
Use a função \ensuremath{\Varid{\Conid{G}.pictures}} disponibilizada na biblioteca \gloss{Gloss}.
\Problema
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}}) é fácil 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 primeiraleitura
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 no segundo grau a $x^2 + b x + c$ em \ensuremath{\N_0}.
Seguindo o método estudado nas aulas\footnote{Secção 3.17 de \cite{Ol18}.},
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
Qual é o assunto desta questão, então? Considerem fórmula que dá a série de Taylor da
função coseno:
\begin{eqnarray*}
cos\ x = \sum_{i=0}^\infty \frac{(-1)^i}{(2i)!} x^{2i}
\end{eqnarray*}
Pretende-se o ciclo-\textsf{for} que implementa a função
\ensuremath{\Varid{cos'}\;\Varid{x}\;\Varid{n}} que dá o valor dessa série tomando \ensuremath{\Varid{i}} até \ensuremath{\Varid{n}} inclusivé:
\begin{hscode}\SaveRestoreHook
\column{B}{@{}>{\hspre}l<{\hspost}@{}}%
\column{E}{@{}>{\hspre}l<{\hspost}@{}}%
\>[B]{}\Varid{cos'}\;\Varid{x}\mathrel{=}\cdots \comp \for{\Varid{loop}}\ {\Varid{init}}\;\mathbf{where}\;\cdots {}\<[E]%
\ColumnHook
\end{hscode}\resethooks
%
\textbf{Sugestão}: Começar por estudar muito bem o processo de cálculo dado
no anexo \ref{sec:recmul} para o problema (semelhante) da função exponencial.
\begin{propriedade}
Testes de que \ensuremath{\Varid{cos'}\;\Varid{x}} calcula bem o coseno de \ensuremath{\pi } e o coseno de \ensuremath{\pi \mathbin{/}\mathrm{2}}:
\begin{hscode}\SaveRestoreHook
\column{B}{@{}>{\hspre}l<{\hspost}@{}}%
\column{E}{@{}>{\hspre}l<{\hspost}@{}}%
\>[B]{}\Varid{prop\char95 cos1}\;\Varid{n}\mathrel{=}\Varid{n}\geq \mathrm{10}\Rightarrow\Varid{abs}\;(\Varid{cos}\;\pi \mathbin{-}\Varid{cos'}\;\pi \;\Varid{n})\mathbin{<}\mathrm{0.001}{}\<[E]%
\\
\>[B]{}\Varid{prop\char95 cos2}\;\Varid{n}\mathrel{=}\Varid{n}\geq \mathrm{10}\Rightarrow\Varid{abs}\;(\Varid{cos}\;(\pi \mathbin{/}\mathrm{2})\mathbin{-}\Varid{cos'}\;(\pi \mathbin{/}\mathrm{2})\;\Varid{n})\mathbin{<}\mathrm{0.001}{}\<[E]%
\ColumnHook
\end{hscode}\resethooks
\end{propriedade}
\paragraph{Valorização} Transliterar \ensuremath{\Varid{cos'}} para a linguagem C; compilar
e testar o código. Conseguia, por intuição apenas, chegar a esta função?
\Problema
Pretende-se nesta questão desenvolver uma biblioteca de funções para
manipular \emph{sistemas de ficheiros} genéricos.
Um sistema de ficheiros será visto como uma associação de \emph{nomes}
a ficheiros ou \emph{directorias}.
Estas últimas serão vistas como sub-sistemas de ficheiros e assim
recursivamente.
Assumindo que \ensuremath{\Varid{a}} é o tipo dos identificadores dos ficheiros e
directorias, e que \ensuremath{\Varid{b}} é o tipo do conteúdo dos ficheiros,
podemos definir um tipo indutivo de dados para representar sistemas de
ficheiros da seguinte forma:
\begin{hscode}\SaveRestoreHook
\column{B}{@{}>{\hspre}l<{\hspost}@{}}%
\column{E}{@{}>{\hspre}l<{\hspost}@{}}%
\>[B]{}\mathbf{data}\;\Conid{FS}\;\Varid{a}\;\Varid{b}\mathrel{=}\Conid{FS}\;[\mskip1.5mu (\Varid{a},\Conid{Node}\;\Varid{a}\;\Varid{b})\mskip1.5mu]\;\mathbf{deriving}\;(\Conid{Eq},\Conid{Show}){}\<[E]%
\\
\>[B]{}\mathbf{data}\;\Conid{Node}\;\Varid{a}\;\Varid{b}\mathrel{=}\Conid{File}\;\Varid{b}\mid \Conid{Dir}\;(\Conid{FS}\;\Varid{a}\;\Varid{b})\;\mathbf{deriving}\;(\Conid{Eq},\Conid{Show}){}\<[E]%
\ColumnHook
\end{hscode}\resethooks
Um caminho (\emph{path}) neste sistema de ficheiros pode ser representado pelo
seguinte tipo de dados:
\begin{hscode}\SaveRestoreHook
\column{B}{@{}>{\hspre}l<{\hspost}@{}}%
\column{E}{@{}>{\hspre}l<{\hspost}@{}}%
\>[B]{}\mathbf{type}\;\Conid{Path}\;\Varid{a}\mathrel{=}[\mskip1.5mu \Varid{a}\mskip1.5mu]{}\<[E]%
\ColumnHook
\end{hscode}\resethooks
Assumindo estes tipos de dados, o seguinte termo
\begin{hscode}\SaveRestoreHook
\column{B}{@{}>{\hspre}l<{\hspost}@{}}%
\column{4}{@{}>{\hspre}c<{\hspost}@{}}%
\column{4E}{@{}l@{}}%
\column{5}{@{}>{\hspre}l<{\hspost}@{}}%
\column{20}{@{}>{\hspre}l<{\hspost}@{}}%
\column{21}{@{}>{\hspre}l<{\hspost}@{}}%
\column{E}{@{}>{\hspre}l<{\hspost}@{}}%
\>[B]{}\Conid{FS}\;[\mskip1.5mu (\text{\tt \char34 f1\char34},\Conid{File}\;\text{\tt \char34 Ola\char34}),{}\<[E]%
\\
\>[B]{}\hsindent{5}{}\<[5]%
\>[5]{}(\text{\tt \char34 d1\char34},\Conid{Dir}\;(\Conid{FS}\;[\mskip1.5mu (\text{\tt \char34 f2\char34},\Conid{File}\;\text{\tt \char34 Ole\char34}),{}\<[E]%
\\
\>[5]{}\hsindent{16}{}\<[21]%
\>[21]{}(\text{\tt \char34 f3\char34},\Conid{File}\;\text{\tt \char34 Ole\char34}){}\<[E]%
\\
\>[5]{}\hsindent{15}{}\<[20]%
\>[20]{}\mskip1.5mu])){}\<[E]%
\\
\>[B]{}\hsindent{4}{}\<[4]%
\>[4]{}\mskip1.5mu]{}\<[4E]%
\ColumnHook
\end{hscode}\resethooks
representará um sistema de ficheiros em cuja raíz temos um ficheiro chamado
\ensuremath{\Varid{f1}} com conteúdo \ensuremath{\text{\tt \char34 Ola\char34}} e uma directoria chamada \ensuremath{\text{\tt \char34 d1\char34}} constituída por dois
ficheiros, um chamado \ensuremath{\text{\tt \char34 f2\char34}} e outro chamado \ensuremath{\text{\tt \char34 f3\char34}}, ambos com conteúdo \ensuremath{\text{\tt \char34 Ole\char34}}.
%
Neste caso, tanto o tipo dos identificadores como o tipo do conteúdo dos
ficheiros é \ensuremath{\Conid{String}}. No caso geral, o conteúdo de um ficheiro é arbitrário:
pode ser um binário, um texto, uma colecção de dados, etc.
A definição das usuais funções \ensuremath{\Varid{inFS}} e \ensuremath{\Varid{recFS}} para este tipo é a seguinte:
\begin{hscode}\SaveRestoreHook
\column{B}{@{}>{\hspre}l<{\hspost}@{}}%
\column{E}{@{}>{\hspre}l<{\hspost}@{}}%
\>[B]{}\Varid{inFS}\mathrel{=}\Conid{FS}\comp \map \;(\Varid{id}\times\Varid{inNode}){}\<[E]%
\\
\>[B]{}\Varid{inNode}\mathrel{=}\alt{\Conid{File}}{\Conid{Dir}}{}\<[E]%
\\[\blanklineskip]%
\>[B]{}\Varid{recFS}\;\Varid{f}\mathrel{=}\Varid{baseFS}\;\Varid{id}\;\Varid{id}\;\Varid{f}{}\<[E]%
\ColumnHook
\end{hscode}\resethooks
Suponha que se pretende definir como um \ensuremath{\Varid{catamorfismo}} a função que
conta o número de ficheiros existentes num sistema de ficheiros. Uma
possível definição para esta função seria:
\begin{hscode}\SaveRestoreHook
\column{B}{@{}>{\hspre}l<{\hspost}@{}}%
\column{E}{@{}>{\hspre}l<{\hspost}@{}}%
\>[B]{}\Varid{conta}\mathbin{::}\Conid{FS}\;\Varid{a}\;\Varid{b}\to \Conid{Int}{}\<[E]%
\\
\>[B]{}\Varid{conta}\mathrel{=}\Varid{cataFS}\;(\Varid{sum}\comp \map \;(\alt{\underline{\mathrm{1}}}{\Varid{id}}\comp \p2)){}\<[E]%
\ColumnHook
\end{hscode}\resethooks
O que é para fazer:
\begin{enumerate}
\item Definir as funções \ensuremath{\Varid{outFS}}, \ensuremath{\Varid{baseFS}}, \ensuremath{\Varid{cataFS}}, \ensuremath{\Varid{anaFS}} e \ensuremath{\Varid{hyloFS}}.
\item Apresentar, no relatório, o diagrama de \ensuremath{\Varid{cataFS}}.
\item Definir as seguintes funções para manipulação de sistemas de
ficheiros usando, obrigatoriamente, catamorfismos, anamorfismos ou
hilomorfismos:
\begin{enumerate}
\item Verificação da integridade do sistema de ficheiros (i.e. verificar
que não existem identificadores repetidos dentro da mesma directoria). \\
\ensuremath{\Varid{check}\mathbin{::}\Conid{FS}\;\Varid{a}\;\Varid{b}\to \Conid{Bool}}
\begin{propriedade}
A integridade de um sistema de ficheiros não depende da ordem em que os
últimos são listados na sua directoria:
\begin{hscode}\SaveRestoreHook
\column{B}{@{}>{\hspre}l<{\hspost}@{}}%
\column{E}{@{}>{\hspre}l<{\hspost}@{}}%
\>[B]{}\Varid{prop\char95 check}\mathbin{::}\Conid{FS}\;\Conid{String}\;\Conid{String}\to \Conid{Bool}{}\<[E]%
\\
\>[B]{}\Varid{prop\char95 check}\mathrel{=}\Varid{check}\comp (\Varid{cataFS}\;(\Varid{inFS}\comp \Varid{reverse}))\equiv\Varid{check}{}\<[E]%
\ColumnHook
\end{hscode}\resethooks
\end{propriedade}
\item Recolha do conteúdo de todos os ficheiros num arquivo indexado pelo \emph{path}.\\
\ensuremath{\Varid{tar}\mathbin{::}\Conid{FS}\;\Varid{a}\;\Varid{b}\to [\mskip1.5mu (\Conid{Path}\;\Varid{a},\Varid{b})\mskip1.5mu]}
\begin{propriedade}
O número de ficheiros no sistema deve ser igual ao número de ficheiros
listados pela função \ensuremath{\Varid{tar}}.
\begin{hscode}\SaveRestoreHook
\column{B}{@{}>{\hspre}l<{\hspost}@{}}%
\column{E}{@{}>{\hspre}l<{\hspost}@{}}%
\>[B]{}\Varid{prop\char95 tar}\mathbin{::}\Conid{FS}\;\Conid{String}\;\Conid{String}\to \Conid{Bool}{}\<[E]%
\\
\>[B]{}\Varid{prop\char95 tar}\mathrel{=}\length \comp \Varid{tar}\equiv\Varid{conta}{}\<[E]%
\ColumnHook
\end{hscode}\resethooks
\end{propriedade}
\item Transformação de um arquivo com o conteúdo dos ficheiros
indexado pelo \emph{path} num sistema de ficheiros.\\
\ensuremath{\Varid{untar}\mathbin{::}[\mskip1.5mu (\Conid{Path}\;\Varid{a},\Varid{b})\mskip1.5mu]\to \Conid{FS}\;\Varid{a}\;\Varid{b}} \\
\textbf{Sugestão}: Use a função \ensuremath{\Varid{joinDupDirs}} para juntar directorias que estejam na mesma
pasta e que possuam o mesmo identificador.
\begin{propriedade}
A composição \ensuremath{\Varid{tar}\comp \Varid{untar}} preserva o número de ficheiros no sistema.
\begin{hscode}\SaveRestoreHook
\column{B}{@{}>{\hspre}l<{\hspost}@{}}%
\column{E}{@{}>{\hspre}l<{\hspost}@{}}%
\>[B]{}\Varid{prop\char95 untar}\mathbin{::}[\mskip1.5mu (\Conid{Path}\;\Conid{String},\Conid{String})\mskip1.5mu]\to \Conid{Property}{}\<[E]%
\\
\>[B]{}\Varid{prop\char95 untar}\mathrel{=}\Varid{validPaths}\Rightarrow((\length \comp \Varid{tar}\comp \Varid{untar})\equiv\length ){}\<[E]%
\\
\>[B]{}\Varid{validPaths}\mathbin{::}[\mskip1.5mu (\Conid{Path}\;\Conid{String},\Conid{String})\mskip1.5mu]\to \Conid{Bool}{}\<[E]%
\\
\>[B]{}\Varid{validPaths}\mathrel{=}(\equiv \mathrm{0})\comp \length \comp (\Varid{filter}\;(\lambda (\Varid{a},\anonymous )\to \length \;\Varid{a}\equiv \mathrm{0})){}\<[E]%
\ColumnHook
\end{hscode}\resethooks
\end{propriedade}
\item Localização de todos os \emph{paths} onde existe um
determinado ficheiro.\\
\ensuremath{\Varid{find}\mathbin{::}\Varid{a}\to \Conid{FS}\;\Varid{a}\;\Varid{b}\to [\mskip1.5mu \Conid{Path}\;\Varid{a}\mskip1.5mu]}
\begin{propriedade}
A composição \ensuremath{\Varid{tar}\comp \Varid{untar}} preserva todos os ficheiros no sistema.
\begin{hscode}\SaveRestoreHook
\column{B}{@{}>{\hspre}l<{\hspost}@{}}%
\column{7}{@{}>{\hspre}l<{\hspost}@{}}%
\column{E}{@{}>{\hspre}l<{\hspost}@{}}%
\>[B]{}\Varid{prop\char95 find}\mathbin{::}\Conid{String}\to \Conid{FS}\;\Conid{String}\;\Conid{String}\to \Conid{Bool}{}\<[E]%
\\
\>[B]{}\Varid{prop\char95 find}\mathrel{=}\Varid{curry}\mathbin{\$}{}\<[E]%
\\
\>[B]{}\hsindent{7}{}\<[7]%
\>[7]{}\length \comp \uncurry{\Varid{find}}\equiv\length \comp \uncurry{\Varid{find}}\comp (\Varid{id}\times(\Varid{untar}\comp \Varid{tar})){}\<[E]%
\ColumnHook
\end{hscode}\resethooks
\end{propriedade}
\item Criação de um novo ficheiro num determinado \emph{path}.\\
\ensuremath{\Varid{new}\mathbin{::}\Conid{Path}\;\Varid{a}\to \Varid{b}\to \Conid{FS}\;\Varid{a}\;\Varid{b}\to \Conid{FS}\;\Varid{a}\;\Varid{b}}
\begin{propriedade}
A adição de um ficheiro não existente no sistema não origina ficheiros duplicados.
\begin{hscode}\SaveRestoreHook
\column{B}{@{}>{\hspre}l<{\hspost}@{}}%
\column{7}{@{}>{\hspre}l<{\hspost}@{}}%
\column{47}{@{}>{\hspre}l<{\hspost}@{}}%
\column{E}{@{}>{\hspre}l<{\hspost}@{}}%