Free Palestine and Lebanon 🍉 Stop the Genocide
Haskell Logo

Programação Funcional

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)