| M.P.I - 1999/2000 - Trabalho Prático Nr. 1 |
|---|---|
| [ 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 definir um módulo em HASKELL para registo de árvores genealógicas , seu processamento e sua visualização usando um 'browser' de HTML (eg. Netscape, Internet Explorer). Para isso vamos considerar, em primeiro lugar, o tipo indutivo que se segue e que define a estrutura de árvores genealógicas de indíviduos, aqui parametrizados por i:
data ArvGen i = Ind i -- dados sobre indivíduo
(Maybe (ArvGen i )) -- genealogia do pai (caso seja conhecida)
(Maybe (ArvGen i )) -- genealogia da mãe (caso seja conhecida)
Para efeitos de visualização será utilizada uma pequena biblioteca
de funções em HASKELL
, fornecida em anexo, que permite manipular e
visualizar expressões matemáticas sob a forma de tabelas em HTML
.
Essa funcionalidade desenvolve-se à volta do tipo indutivo que se segue:
data Exp v o = Var v -- expressões ou são variáveis
| Term o [ Exp v o ] -- ou termos envolvendo operadores e
-- subtermos
deriving Show
Por exemplo,
a expressão
x + y * (-z²)
poderá ser descrita sob a forma do seguinte valor de Exp:
Term "+" [Var "x",Term "*" [Var "y",Term "-" [Term "sq" [Var "z"]]]]
e visualizada em HTML
da forma
| + | x | ||
| * | y | ||
| - | sq | z | |
Com base no código fornecido em apêndice, satisfaça os requisitos que a seguir se enunciam e que têm a ver com o tipo Exp.
Term "+" [(Var 1),(Var 2)]
deverá dar como resultado o valor 3.
data Ind1 = I1 {name1 :: String, -- nome
date1 :: Integer} -- data de nascimento
data Ind2 = I2 {name2 :: String, -- nome
surname2:: String, -- apelido
date2 :: Integer} -- data de nascimento
defina uma função que calcule a maior lista de apelidos que o
indivíduo raíz da árvore pode ter.
Para isso, considere a seguinte regra de construção de apelidos:
o apelido de um indivíduo é obtido concatenando a lista dos apelidos
da mãe com a lista dos apelidos do pai.
Por exemplo,
de acordo com essa regra
o «Pedro Matos Silva» da árvore
| Pedro Matos Silva | João Silva | Manuel Silva |
| Maria Mendes | |
| Teresa Matos | Augusto Matos |
| Luísa Santos | |
Por fim, pretende-se mapear a estrutura ArvGen em Exp por forma a tirar partido da funcionalidade que permite visualizar expressões em HTML . A partir desse mapeamento, definido através de uma função arvGen2Exp, deverá ser construída uma funcionalidade que permita visualizar a árvore genealógica de um indivíduo em formato HTML . Por exemplo, a visualização acima da árvore genealógica de «Pedro Matos Silva» poderá ser obtida a partir da conversão da respectiva árvore genealógica para a expressão
Term "Pedro Matos Silva" [
Term "João Silva" [Var "Manuel Silva", Var "Maria Mendes"],
Term "Teresa Matos" [Var "Augusto Matos", Var "Luísa Santos"]
]
-- (c) MP-I 99/00 -- Material para 1.o Trabalho Prático
-- tipos de dados
data ArvGen i = Ind i -- dados sobre indivíduo
(Maybe (ArvGen i )) -- genealogia do pai (se for conhecida)
(Maybe (ArvGen i )) -- genealogia da mãe (se for conhecida)
data Exp v o = Var v -- expressões ou são variáveis
| Term o [ Exp v o ] -- ou termos envolvendo operadores e
-- subtermos
deriving Show
data Cell a = ICell a Int Int | LCell a Int Int deriving Show
type Html a = [ Cell a ]
data Txt = Str String | Blk [ Txt ] deriving Show
-- funções
txtFlat (Str s) = [s]
txtFlat (Blk []) = []
txtFlat (Blk (a:l)) = txtFlat a ++ txtFlat (Blk l)
expFold :: (a -> b) -> (c -> [b] -> b) -> Exp a c -> b
expFold f g (Var e) = f e
expFold f g (Term o l) = g o (map (expFold f g) l)
expLeaves = expFold singl h
where singl a = [a]
h o l = foldr (++) [] l
expWidth = length . expLeaves
expDepth = expFold (const 1) h
where h o x = (succ . (foldr max 0)) x
exp2Html n (Var e) = f n e
where f n a = [ LCell a n 1 ]
exp2Html n (Term o l) = g (Term o l) o (map (exp2Html m) l)
where g x a b = [ ICell a 1 (expWidth x) ] ++ (foldr (++) [] b)
m = expDepth (Term o l) - 1
html2Txt :: (a -> Txt) -> Html a -> Txt
html2Txt f = html . table . (foldr g u)
where u = Str "\n</tr>"
g c (Str s) = g c (Blk [Str s])
g (ICell a x y) (Blk b) = Blk ([ cell (f a) x y ] ++ b)
g (LCell a x y) (Blk b) = Blk ([ cell (f a) x y, Str "\n</tr>\n<tr>"] ++ b)
html t = Blk [ Str("<html>\n<body bgcolor=\"#F4EFD8\" " ++
"text=\"#260000\" link=\"#008000\" " ++
"vlink=\"#800000\">\n"),
t,
Str "<html>\n"
]
table t = Blk [ Str "<table border=1 cellpadding=1 cellspacing=0>",
t,
Str "</table>\n"
]
cell c x y = Blk [ Str("\n<td rowspan=" ++
itoa y ++
" colspan=" ++
itoa x ++
" align=\"center\"" ++
">\n"),
c,
Str "\n</td>"
]
itoa x = show x
expDisplay fn =
(writeFile fn) . (foldr (++) []) . txtFlat . (html2Txt Str) . (exp2Html 1)