Ficha 3: Gestão de informação em listas
Voltar
1) Assumindo que uma hora é representada por um par de inteiros, uma viagem pode ser representada por uma sequência de etapas, onde cada etapa é representada por um par de horas (partida, chegada):
data Hora = H Int Int
deriving Show
type Etapa = (Hora,Hora)
type Viagem = [Etapa]
Por exemplo, se uma viagem for [(H 9 30, H 10 25), (H 11 20, H 12 45), (H 13 30, H 14 45)]
significa que teve três etapas:
- a primeira começou às 9 e um quarto e terminou às 10 e 25;
- a segunda começou às 11 e 20 e terminou à uma menos um quarto;
- a terceira começou às 1 e meia e terminou às 3 menos um quarto;
Para este problema, vamos trabalhar apenas com viagens que começam e acabam no mesmo dia. Utilizando as funções sobre horas que definiu na Ficha 1, defina as seguintes funções:
a) Testar se uma etapa está bem construída (i.e., o tempo de chegada é superior ao de partida e as horas são válidas).
etapaBemConstruida :: Etapa -> Bool
etapaBemConstruida (h1,h2) = horaValida h1 && horaValida h2 && horaDepoisDe h2 h1
b) Testa se uma viagem está bem construída (i.e., se para cada etapa, o tempo de chegada é superior ao de partida, e se a etapa seguinte começa depois da etapa anterior ter terminado).
viagemBemConstruida :: Viagem -> Bool
viagemBemConstruida [] = True
viagemBemConstruida ((h1,h2):t) = etapaBemConstruida (h1,h2) && viagemBemConstruida t &&
(case t of [] -> True
(h3,h4):t' -> h3 `horaDepoisDe` h2)
viagemBemConstruida' :: Viagem -> Bool
viagemBemConstruida' [] = True
viagemBemConstruida' [e] = etapaBemConstruida e
viagemBemConstruida' ((h1,h2):t) = etapaBemConstruida (h1,h2) && viagemBemConstruida' t && h3 `horaDepoisDe` h2
where (h3,h4) = head t
c) Calcular a hora de partida e de chegada de uma dada viagem.
partidaEChegada :: Viagem -> (Hora,Hora)
partidaEChegada v = (hi,hf)
where (hi,_) = head v
(_,hf) = last v
d) Dada uma viagem válida, calcular o tempo total de viagem efectiva.
tempoViagemEfetiva :: Viagem -> Hora
tempoViagemEfetiva [] = H 0 0
tempoViagemEfetiva ((h1,h2):t) = adicionaHoras (diferencaHoras h2 h1) (tempoDeViagem t)
adicionaHoras :: Hora -> Hora -> Hora
adicionaHoras (H h1 m1) (H h2 m2) = H (h1 + h2 + hExtra) (mod (m1 + mr) 60)
where hExtra = div (m1 + m2) 60
e) Calcular o tempo total de espera.
tempoEspera :: Viagem -> Hora
tempoEspera ((h1,h2):(h3,h4):t) = adicionaHoras (diferencaHoras h3 h2) (tempoDeEspera ((h3,h4):t))
tempoEspera _ = H 0 0
f) Calcular o tempo total da viagem (a soma dos tempos de espera e de viagem efectiva).
tempoTotalViagem :: Viagem -> Hora
tempoTotalViagem v = adicionaHoras (tempoViagemEfetiva v) (tempoEspera v)
tempoTotalViagem' :: Viagem -> Hora
tempoTotalViagem' v = diferencaHoras hf hi
where (hi,hf) = partidaEChegada v
2) Considere as seguinte definição de um tipo para representar linhas poligonais.
type Poligonal = [Ponto]
O tipo Ponto
é idêntico ao definido na Ficha 1. Nas resolução das alíneas seguintes pode utilizar funções definidas nessa ficha.
a) Defina a função para calcular o comprimento de uma linha poligonal
comprimento :: Poligonal -> Double
comprimento (p1:p2:t) = dist p1 p2 + comprimento (p2:t)
comprimento _ = 0
b) Defina uma função para testar se uma dada linha poligonal é ou não fechada.
linhaFechada :: Poligonal -> Bool
linhaFechada p = length p >= 3 && head p == last p
c) Defina a função triangula :: Poligonal -> [Figura]
que, dada uma linha poligonal fechada e convexa, calcule uma lista de triângulos cuja soma das áreas seja igual à àrea delimitada pela linha poligonal. O tipo Figura
é idêntico ao definido na Ficha 1.
triangula :: Poligonal -> [Figura]
triangula (p1:p2:p3:ps)
| p1 == p3 = []
| otherwise = Triangulo p1 p2 p3 : triangula (p1:p3:ps)
triangula _ = []
d) Defina uma função para calcular a área delimitada por uma linha poligonal fechada e convexa.
areaPol :: Poligonal -> Double
areaPol p = areaTris (triangula p)
areaTris :: [Figura] -> Double
areaTris [] = 0
areaTris (h:t) = area h + areaTris t
e) Defina a função mover :: Poligonal -> Ponto -> Poligonal
que, dada uma linha poligonal e um ponto, dá como resultado uma linha poligonal idêntica à primeira mas tendo como ponto inicial o ponto dado.
mover :: Poligonal -> Ponto -> Poligonal
mover pol p = p : pol
f) Defina a função zoom :: Double -> Poligonal -> Poligonal
que, dada um fator de escala e uma linha poligonal, dê como resultado uma linha poligonal semelhante e com o mesmo ponto inicial mas em que o comprimento de cada segmento de reta é multiplicado pelo fator dado.
zoom :: Double -> Poligonal -> Poligonal
zoom z (h:t) = mover (doZoom z h t) h
doZoom :: Double -> Ponto -> Poligonal -> Poligonal
doZoom z p [] = []
doZoom z p (h:t) = Cartesiano ((x - xp) * z + xp) ((y - yp) * z + yp) : doZoom z p t
where x = posx h
y = posy h
xp = posx p
yp = posy p
3) Para armazenar uma agenda de contactos telefónicos e de correio electrónico definiram-se os seguintes tipos de dados. Não existem nomes repetidos na agenda e para cada nome existe uma lista de contactos.
data Contacto = Casa Integer
| Trab Integer
| Tlm Integer
| Email String
deriving Show
type Nome = String
type Agenda = [(Nome, [Contacto])]
a) Defina a função acrescEmail :: Nome -> String -> Agenda -> Agenda
que, dado um nome, um email e uma agenda, acrescenta essa informação à agenda.
acrescEmail :: Nome -> String -> Agenda -> Agenda
acrescEmail nome email [] = [(nome, [email])]
acrescEmail nome email ((n,cs):t)
| nome == n = (n, email : cs) : t
| otherwise = (n,cs) : acrescEmail nome email t
b) Defina a função verEmails :: Nome -> Agenda -> Maybe [String]
que, dado um nome e uma agenda, retorna a lista dos emails associados a esse nome. Se esse nome não existir na agenda a função deve retornar Nothing
.
verEmails :: Nome -> Agenda -> Maybe [String]
verEmails _ [] = Nothing
verEmails nome ((n,cs):t)
| nome == n = Just (soEmails cs)
| otherwise = verEmails nome t
soEmails :: [Contacto] -> [String]
soEmails [] = []
soEmails (Email e : t) = e : soEmails t
soEmails (_:t) = soEmails t
c) Defina a função consTelefs :: [Contacto] -> [Integer]
que, dada uma lista de contactos, retorna a lista de todos os números de telefone dessa lista (tanto telefones fixos como telemóveis).
consTelefs :: [Contacto] -> [Integer]
consTelefs [] = []
consTelefs (Email _:cs) = consTelefs cs
consTelefs (c:cs) = c : consTelefs cs
d) Defina a função casa :: Nome -> Agenda -> Maybe Integer
que, dado um nome e uma agenda, retorna o número de telefone de casa (caso exista).
casa :: Nome -> Agenda -> Maybe Integer
casa _ [] = Nothing
casa nome ((n,cs):t)
| nome == n = numCasa cs
| otherwise = casa nome t
numCasa :: [Contacto] -> Maybe Integer
numCasa [] = Nothing
numCasa (Casa n : t) = Just n
numCasa (_:t) = numCasa t
4) Pretende-se guardar informação sobre os aniversários das pessoas numa tabela que associa o nome de cada pessoa à sua data de nascimento. Para isso, declarou-se a seguinte estrutura de dados:
type Dia = Int
type Mes = Int
type Ano = Int
type Nome = String
data Data = D Dia Mes Ano
deriving Show
type TabDN = [(Nome,Data)]
a) Defina a função procura :: Nome -> TabDN -> Maybe Data
que indica a data de nascimento de uma dada pessoa, caso o seu nome exista na tabela.
procura :: Nome -> TabDN -> Maybe Data
procura _ [] = Nothing
procura nome ((n,d):ts) = if nome == n then Just d else procura nome ts
b) Defina a função idade :: Data -> Nome -> TabDN -> Maybe Int
que calcula a idade de uma pessoa numa dada data.
idade :: Data -> Nome -> TabDN -> Maybe Int
idade _ _ [] = Nothing
idade (D dx mx ax) nome ((n,D d m a):ts)
| nome == n = Just (calculaIdade (D d m a) (D dx mx ax))
| otherwise = idade (D dx mx ax) nome ts
calculaIdade :: Data -> Data -> Int
calculaIdade (D dn mn an) (D d m a) = if m > mn || m == mn && d > dn then a - an else a - an - 1
c) Defina a função anterior :: Data -> Data -> Bool
que testa se uma data é anterior a outra data.
anterior :: Data -> Data -> Bool
anterior (D d m a) (D d2 m2 a2) = a < a2 || (a == a2 && (m < m2 || (m == m2 && d < d2)))
d) Defina a função ordena :: TabDN -> TabDN
que ordena uma tabela de datas de nascimento por ordem crescente das datas de nascimento.
ordena :: TabDN -> TabDN
ordena [] = []
ordena ((n,d):ts) = insereDN (n,d) (ordena ts)
insereDN :: (Nome,Data) -> TabDN -> TabDN
insereDN (n,d) [] = [(n,d)]
insereDN (n,d) ((nh,dh):t) | anterior d dh = (n,d) : (nh,dh) : t
| otherwise = (nh,dh) : insereDN (n,d) t
e) Defina a função porIdade:: Data -> TabDN -> [(Nome,Int)]
que apresenta o nome e a idade das pessoas, numa dada data, por ordem crescente da idade das pessoas.
porIdade :: Data -> TabDN -> [(Nome,Int)]
porIdade data tabela = porIdadeAux data (ordena tabela)
porIdadeAux :: Data -> TabDN -> [(Nome,Int)]
porIdadeAux _ [] = []
porIdadeAux d ((nh,dh):t) = porIdadeAux d t ++ [(nh, calculaIdade dh d)]
5) Considere o seguinte tipo de dados que descreve a informação de um extrato bancário. Cada valor deste tipo indica o saldo inicial e uma lista de movimentos. Cada movimento é representado por um triplo que indica a data da operação, a sua descrição e a quantia movimentada (em que os valores são sempre números positivos).
data Movimento = Credito Float | Debito Float
deriving Show
data Data = D Int Int Int
deriving Show
data Extracto = Ext Float [(Data, String, Movimento)]
deriving Show
a) Construa a função extValor :: Extracto -> Float -> [Movimento]
que produz uma lista de todos os movimentos (créditos ou débitos) superiores a um determinado valor.
extValor :: Extracto -> Float -> [Movimento]
extValor (Ext si ((_,_,mov):t)) valor = if getValor mov > valor then mov : extValor (Ext si t) valor else extValor (Ext si t) valor
getValor :: Movimento -> Float
getValor (Credito x) = x
getValor (Debito x) = x
b) Defina a função filtro :: Extracto -> [String] -> [(Data,Movimento)]
que retorna informação relativa apenas aos movimentos cuja descrição esteja incluída na lista fornecida no segundo parâmetro.
filtro :: Extracto -> [String] -> [(Data,Movimento)]
filtro (Ext _ []) _ = []
filtro (Ext si ((data,desc,mov):t)) listaStr = if desc `elem` listaStr then (data,mov) : filtro (Ext si t) listaStr else filtro (Ext si t) listaStr
c) Defina a função creDeb :: Extracto -> (Float,Float)
que retorna o total de créditos e de débitos de um extrato no primeiro e segundo elementos de um par, respectivamente.
creDeb :: Extracto -> (Float,Float)
creDeb (Ext _ []) = (0,0)
creDeb (Ext si ((_,_,Credito x):t)) = (x + cr, dr)
where (cr,dr) = creDeb (Ext si t)
creDeb (Ext si ((_,_,Debito x):t)) = (cr, x + dr)
where (cr,dr) = creDeb (Ext si t)
creDeb' :: Extracto -> (Float,Float)
creDeb' (Ext _ []) = (0,0)
creDeb' (Ext si ((_,_,mov):t)) = (c + cr, d + dr)
where (cr,dr) = creDeb (Ext si t)
(c,d) = case mov of Credito x -> (x,0)
Debito x -> (0,x)
a) Defina a função saldo :: Extracto -> Float
que devolve o saldo final que resulta da execução de todos os movimentos no extrato sobre o saldo inicial.
saldo :: Extracto -> Float
saldo (Ext si []) = si
saldo (Ext si ((_,_,Debito x):t)) = saldo (Ext (si + x) t)
saldo (Ext si ((_,_,Credito x):t)) = saldo (Ext (si - x) t)