M.P.-I 2000/01: Trabalho Prático Nr. 3
[ DI/UM ]

Preâmbulo

Este trabalho deve ser realizado por grupos com um máximo de três alunos. O trabalho deve ser entregue até ao dia 20 de Dezembro de 2000 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.

Objectivo

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))

Requisitos

1. Apresente, no seu relatório, o diagrama de cataFS.

2. Defina as usuais funções anaFS e hyloFS.

3. Declare FS como instância da classe BiFunctor (ver Mpi.hs).

4. Defina as seguintes funções para manipulação de sistemas de ficheiros usando, obrigatoriamente, catamorfismos, anamorfismos ou hilomorfismos:
   1. Verificação da integridade do sistema de ficheiros (i.é, verificar que não existem identificadores repetidos dentro da mesma directoria).
      check :: FS a b -> Bool
   2. Recolha do conteúdo de todos os ficheiros num arquivo indexado pelo path.
      tar :: FS a b -> [(Path a, b)]
   3. Transformação de um arquivo com o conteúdo dos ficheiros indexado pelo path num sistema de ficheiros (inversa da anterior).
      untar :: [(Path a, b)] -> FS a b
   4. Listagem de todos os identificadores acessíveis a partir de um determinado path.
      ls :: Path a -> FS a b -> [a]
   5. Localização de todos os paths onde existe um determinado ficheiro.
      find :: a -> FS a b -> [Path a]
   6. Criação de um novo ficheiro num determinado path.
      new :: Path a -> b -> FS a b -> FS a b
   7. Duplicação de um ficheiro.
      cp :: Path a -> Path a -> FS a b -> FS a b
   8. Eliminação de um ficheiro.
      rm :: Path a -> FS a b -> FS a b
   9. Cálculo do espaço total ocupado pelos ficheiros de um sistema de ficheiros. Esta função deve receber como parâmetro uma função que permite calcular o tamanho de um ficheiro (por exemplo, se o conteudo dos ficheiros for do tipo String esta função seria o length).
      du :: (b -> Int) -> FS a b -> Int

Valorização

1. Função de visualização da estrutura em árvore de um sistema de ficheiros num 'browser' de HTML (eg. Netscape, Internet Explorer). Sugere-se uma abordagem semelhante à da que é realizada em demoBTree.hs para visualização de árvores em funções como, por exemplo, qSort_in_html e hanoi_run_in_html.

   Para o sistema de ficheiros exemplo apresentado em cima, poderá obter-se qualquer coisa como

   	f1	Ola
   	d1	f2	Ole
   		f3	Ole

2. 'Shell' de ligação da aplicação desenvolvida ao sistema de ficheiros real da máquina em que está a correr.