M.P.-I 2000/01: Trabalho Prático Nr. 3 | |
---|---|
[ DI/UM ] |
Este trabalho deve ser realizado por grupos com um máximo de três alunos. O trabalho deve ser entregue até ao dia na Recepção do Departamento de Informática (ext. 4430) e nele deve constar a listagem do código desenvolvido assim como um pequeno relatório.
Pretende-se com este trabalho desenvolver uma biblioteca de funções 'point-free' para manipular sistemas de ficheiros genéricos.
Um sistema de ficheiros será visto como uma associação de nomes a ficheiros ou directorias. Estas últimas serão vistas como sub-sistemas de ficheiros e assim recursivamente. Assumindo que a é o tipo dos identificadores dos ficheiros e directorias e que b é o tipo do conteúdo dos ficheiros, podemos definir um tipo indutivo de dados para representar sistemas de ficheiros da seguinte forma:
data FS a b = FS [(a,Node a b)] data Node a b = File b | Dir (FS a b)
Um path neste sistema de ficheiros pode ser representado pelo seguinte tipo de dados:
type Path a = [a]
Dado este tipo de dados, o seguinte termo representa um sistema de ficheiros em cuja raíz temos um ficheiro chamado f1 com conteúdo Ola e uma directoria chamada d1 constituída por dois ficheiros, um chamado f2 e outro chamado f3, ambos com conteúdo Ole:
FS [("f1", File "Ola"), ("d1", Dir (FS [("f2", File "Ole"), ("f3", File "Ole") ])) ]
Neste caso, tanto o tipo dos identificadores como o tipo do conteúdo dos ficheiros é 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 inFS, outFS, recFS e cataFS para este tipo é a seguinte:
inFS = FS . map (id >< inNode) inNode = either File Dir outFS (FS l) = map (id >< outNode) l outNode (File b) = Left b outNode (Dir fs) = Right fs recFS f = map (id >< (id -|- f)) cataFS g = g . recFS (cataFS g) . outFS
Suponha que se pretendia definir como um 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:
conta :: FS a b -> Int conta = cataFS (sum . map ((either (const 1) id) . snd))
Para o sistema de ficheiros exemplo apresentado em cima, poderá obter-se qualquer coisa como
f1 | Ola | |
d1 | f2 | Ole |
f3 | Ole | |