Free Palestine and Lebanon 🍉 Stop the Genocide
Haskell Logo

Programação Funcional

Ficha 2: Funções recursivas sobre listas

Voltar

1) Indique como é que o interpretador de Haskell avalia as expressões das alíneas que se seguem, apresentando a cadeia de redução de cada uma dessas expressões (i.e., os vários passos intermédios até se chegar ao valor final)

a) Considere a seguinte definição:

funA :: [Double] -> Double
funA [] = 0
funA (y:ys) = y ^ 2 + (funA ys)

Diga, justificando, qual é o valor de funA [2,3,5,1].

funA [2,3,5,1]
    = funA (2:[3,5,1])
    = 2 ^ 2 + (funA [3,5,1])
    = 4 + funA (3:[5,1])
    = 4 + 3 ^ 2 + (funA [5,1])
    = 4 + 9 + funA (5:[1])
    = 13 + 5 ^ 2 + (funA [1])
    = 13 + 25 + funA (1:[])
    = 38 + 1 ^ 2 + (funA [])
    = 38 + 1 + 0
    = 39

b) Considere a seguinte definição:

funB :: [Int] -> [Int]
funB [] = []
funB (h:t) = if mod h 2 == 0 
             then h : funB t
             else funB t

Diga, justificando, qual é o valor de funB [8,5,2].

funB [8,5,2] 
    = funB (8:[5,2]) -- mod 8 2 = 0
    = 8 : funB [5,2]
    = 8 : funB (5:[2]) -- mod 5 2 = 1
    = 8 : funB [2]
    = 8 : funB (2:[]) -- mod 2 2 = 0
    = 8 : 2 : funB []
    = 8 : 2 : []
    = [8,2]

c) Considere a seguinte definição:

funC (x:y:t) = funC t
funC [x] = [x]
funC [] = []

Diga, justificando, qual é o valor de funC [1,2,3,4,5].

funC [1,2,3,4,5]
    = funC (1:2:[3,4,5])
    = funC [3,4,5]
    = funC (3:4:[5])
    = funC [5]
    = [5]

d) Considere a seguinte definição:

funD l = g [] l
g acc [] = acc
g acc (h:t) = g (h:acc) t

Diga, justificando, qual é o valor de funD "otrec".

funD "otrec"
    = g [] "otrec"
    = g [] ('o':"trec")
    = g ('o':[]) "trec"
    = g "o" ('t':"rec")
    = g ('t':"o") "rec"
    = g "to" ('r':"ec")
    = g ('r':"to") "ec"
    = g "rto" ('e':"c")
    = g ('e':"rto") "c"
    = g "erto" ('c':[])
    = g ('c':"erto") []
    = "certo"

2) Defina recursivamente as seguintes funções sobre listas:

a) dobros :: [Float] -> [Float] que recebe uma lista e produz a lista em que cada elemento é o dobro do valor correspondente na lista de entrada.

dobros :: [Float] -> [Float]
dobros [] = []
dobros (h:t) = h * 2 : dobros t

b) numOcorre :: Char -> String -> Int que calcula o número de vezes que um caracter ocorre numa string.

numOcorre :: Char -> String -> Int
numOcorre _ "" = 0
numOcorre c (h:t) = if c == h
                    then 1 + numOcorre c t
                    else numOcorre c t

c) positivos :: [Int] -> Bool que testa se uma lista só tem elementos positivos.

positivos :: [Int] -> Bool
positivos [] = True
positivos (h:t) = if h <= 0
                  then False
                  else positivos t

d) soPos :: [Int] -> [Int] que retira todos os elementos não positivos de uma lista de inteiros.

soPos :: [Int] -> [Int]
soPos [] = []
soPos (h:t)
    | h > 0 = h : soPos t
    | otherwise = soPos t

e) somaNeg :: [Int] -> Int que soma todos os números negativos da lista de entrada.

somaNeg :: [Int] -> Int
somaNeg [] = 0
somaNeg (h:t)
    | h < 0 = h + somaNeg t
    | otherwise = somaNeg t

f) tresUlt :: [a] -> [a] devolve os últimos três elementos de uma lista. Se a lista de entrada tiver menos de três elementos, devolve a própria lista.

tresUlt :: [a] -> [a]
tresUlt [] = []
tresUlt (h:t)
    | length t < 3 = h:t
    | otherwise = tresUlt t

g) segundos :: [(a,b)] -> [b] que calcula a lista das segundas componentes dos pares.

segundos :: [(a,b)] -> [b]
segundos [] = []
segundos ((_,h2):t) = h2 : segundos t

h) nosPrimeiros :: (Eq a) => a -> [(a,b)] -> Bool que testa se um elemento aparece na lista como primeira componente de algum dos pares.

nosPrimeiros :: (Eq a) => a -> [(a,b)] -> Bool
nosPrimeiros _ [] = False
nosPrimeiros x ((h1,_):t) = x == h1 || nosPrimeiros x t

i) sumTriplos :: (Num a, Num b, Num c) => [(a,b,c)] -> (a,b,c) soma uma lista de triplos componente a componente.

Por exemplo, sumTriplos [(2,4,11), (3,1,-5), (10,-3,6)] = (15,2,12).

sumTriplos :: (Num a, Num b, Num c) => [(a,b,c)] -> (a,b,c)
sumTriplos [] = (0,0,0)
sumTriplos ((a,b,c):t) = (a+ra, b+rb, c+rc)
    where (ra,rb,rc) = sumTriplos t

3) Recorrendo a funções do módulo Data.Char, defina recursivamente as seguintes funções sobre strings:

a) soDigitos :: [Char] -> [Char] que recebe uma lista de caracteres e seleciona dessa lista os caracteres que são algarismos.

soDigitos :: [Char] -> [Char]
soDigitos [] = []
soDigitos (h:t)
    | isDigit h = h : soDigitos t
    | otherwise = soDigitos t

b) minusculas :: [Char] -> Int que recebe uma lista de caracteres e conta quantos desses caracteres são letras minúsculas.

minusculas :: [Char] -> Int
minusculas [] = 0
minusculas (h:t)
    | isLower h = 1 + minusculas t
    | otherwise = minusculas t

c) nums :: String -> [Int] que recebe uma string e devolve uma lista com os algarismos que ocorrem nessa string, pela mesma ordem.

nums :: String -> [Int]
nums "" = []
nums (h:t)
    | isDigit h = digitToInt h : nums t
    | otherwise = nums t

4) Uma forma de representar polinómios de uma variável é usar listas de monómios representados por pares (coeficiente, expoente)

type Polinomio = [Monomio]
type Monomio = (Float,Int)

Por exemplo, [(2,3), (3,4), (5,3), (4,5)] representa o polinómio 2x^3 + 3x^4 + 5x^3 + 4x^5 Defina as seguintes funções:

a) conta :: Int -> Polinomio -> Int de forma a que conta n p indica quantos monómios de grau n existem em p.

conta :: Int -> Polinomio -> Int
conta _ [] = 0
conta n ((coeficiente,grau):t)
    | n == grau = 1 + conta n t
    | otherwise = conta n t

b) grau :: Polinomio -> Int que indica o grau de um polinómio.

grau :: Polinomio -> Int
grau [] = 0
grau ((c,g):t)
    | g > grau t = g
    | otherwise = grau t

c) selgrau :: Int -> Polinomio -> Polinomio que selecciona os monómios com um dado grau de um polinómio.

selgrau :: Int -> Polinomio -> Polinomio
selgrau _ [] = []
selgrau n ((c,g):t)
    | n == g = (c,g) : selgrau n t
    | otherwise = selgrau n t

d) deriv :: Polinomio -> Polinomio que calcula a derivada de um polinómio.

deriv :: Polinomio -> Polinomio
deriv [] = []
deriv ((c,g):t)
    | g == 0 = deriv t
    | otherwise = (c * fromIntegral g,g-1) : deriv t

e) calcula :: Float -> Polinomio -> Float que calcula o valor de um polinómio para um dado valor de x.

calcula :: Float -> Polinomio -> Float
calcula _ [] = 0
calcula x ((c,g):t) = c * (x ^ g) + calcula x t

f) simp :: Polinomio -> Polinomio que retira de um polinómio os monómios de coeficiente zero.

simp :: Polinomio -> Polinomio
simp [] = []
simp ((c,g):t)
    | c == 0 = simp t
    | otherwise = (c,g) : simp t

g) mult :: Monomio -> Polinomio -> Polinomio que calcula o resultado da multiplicação de um monómio por um polinómio.

mult :: Monomio -> Polinomio -> Polinomio
mult _ [] = []
mult (cm,gm) ((c,g):t) = (cm * c, gm + g) : mult (cm,gm) t

h) normaliza :: Polinomio -> Polinomio que dado um polinómio constrói um polinómio equivalente em que não podem aparecer vários monómios com o mesmo grau.

normaliza :: Polinomio -> Polinomio
normaliza [] = []
normaliza ((c,g):t) = normalizaAux (c,g) (normaliza t)

normalizaAux :: Monomio -> Polinomio -> Polinomio
normalizaAux m [] = [m]
normalizaAux (cm,gm) ((c,g):t)
    | gm == g = (cm + c,g) : t
    | otherwise = (c,g) : normalizaAux (cm,gm) t

i) soma :: Polinomio -> Polinomio -> Polinomio que soma dois polinómios de forma a que se os polinómios que recebe estiverem normalizados produz também um polinómio normalizado.

soma :: Polinomio -> Polinomio -> Polinomio
soma p [] = p
soma [] p = p
soma ((c,g):t) p = somaAux (c,g) (soma t p)

somaAux :: Monomio -> Polinomio -> Polinomio
somaAux m [] = [m]
somaAux (cm,gm) ((c,g):t)
    | gm == g = (cm + c,g) : t
    | otherwise = (c,g) : somaAux (cm,gm) t

j) produto :: Polinomio -> Polinomio -> Polinomio que calcula o produto de dois polinómios.

produto :: Polinomio -> Polinomio -> Polinomio
produto [] _ = []
produto (m:t) p = (mult m p) ++ produto t p

k) ordena :: Polinomio -> Polinomio que ordena um polinómio por ordem crescente dos graus dos seus monómios.

ordena :: Polinomio -> Polinomio
ordena [] = []
ordena (m:t) = insere m (ordena t)

insere :: Monomio -> Polinomio -> Polinomio
insere m [] = [m]
insere (cm,gm) ((c,g):t)
    | g > gm = (cm,gm) : (c,g) : t
    | otherwise = (c,g) : insere (cm,gm) t

l) equiv :: Polinomio -> Polinomio -> Bool que testa se dois polinómios são equivalentes.

equiv :: Polinomio -> Polinomio -> Bool
equiv p1 p2 = ordena (normaliza p1) == ordena (normaliza p2)