Ficha 5: Funções de ordem superior

Voltar

1) Apresente definições das seguintes funções de ordem superior, já pré-definidas no `Prelude` ou no `Data.List`:

a) `any :: (a -> Bool) -> [a] -> Bool` que testa se um predicado é verdade para algum elemento de uma lista; por exemplo: `any odd [1..10] == True`.

any :: (a -> Bool) -> [a] -> Bool
any f [] = False
any f (h:t) = f h || any f t

b) `zipWith :: (a->b->c) -> [a] -> [b] -> [c]` que combina os elementos de duas listas usando uma função específica; por exemplo: `zipWith (+) [1,2,3,4,5] [10,20,30,40] == [11,22,33,44]`.

zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith f (a:as) (b:bs) = f a b : zipWith f as bs
zipWith _ _ _ = []

c) `takeWhile :: (a->Bool) -> [a] -> [a]` que determina os primeiros elementos da lista que satisfazem um dado predicado; por exemplo: `takeWhile odd [1,3,4,5,6,6] == [1,3]`.

takeWhile :: (a -> Bool) -> [a] -> [a]
takeWhile _ [] = []
takeWhile f (h:t) 
    | f h = h : takeWhile f t
    | otherwise = []

d) `dropWhile :: (a->Bool) -> [a] -> [a]` que elimina os primeiros elementos da lista que satisfazem um dado predicado; por exemplo: `dropWhile odd [1,3,4,5,6,6] == [4,5,6,6]`.

dropWhile :: (a -> Bool) -> [a] -> [a]
dropWhile _ [] = []
dropWhile f (h:t) 
    | f h = dropWhile f t
    | otherwise = h:t

e) `span :: (a-> Bool) -> [a] -> ([a],[a])` que calcula simultaneamente os dois resultados anteriores. Note que apesar de poder ser definida à custa das outras duas, usando a definição:

`span p l = (takeWhile p l, dropWhile p l)`

nessa definição há trabalho redundante que pode ser evitado. Apresente uma definição alternativa onde não haja duplicação de trabalho.

span :: (a-> Bool) -> [a] -> ([a],[a])
span _ [] = ([],[])
span f (h:t) 
    | f h = let (taken, dropped) = span f t in (h:taken, dropped)             
    | otherwise = ([], h:t)

f) `deleteBy :: (a -> a -> Bool) -> a -> [a] -> [a]` que apaga o primeiro elemento de uma lista que é “igual” a um dado elemento de acordo com a função de comparação que é passada como parâmetro. Por exemplo: `deleteBy (\x y -> snd x == snd y) (1,2) [(3,3),(2,2),(4,2)] == [(3,3),(4,2)]`.

deleteBy :: (a -> a -> Bool) -> a -> [a] -> [a]
deleteBy f x (h:t) 
    | f x h = t
    | otherwise = h : deleteBy f x t

g) `sortOn :: Ord b => (a -> b) -> [a] -> [a]` que ordena uma lista comparando os resultados de aplicar uma função de extração de uma chave a cada elemento de uma lista. Por exemplo: `sortOn fst [(3,1),(1,2),(2,5)] == [(1,2),(2,5),(3,1)]`.

sortOn :: (Ord b) => (a -> b) -> [a] -> [a]
sortOn f [] = []
sortOn f (h:t) = insertOn f h (sortOn f t)
    
insertOn :: (Ord b) => (a -> b) -> a -> [a] -> [a]
insertOn _ x [] = [x]
insertOn f x (h:t) = if f x > f h then h : insertOn f x t else x : h : t

2) Relembre a questão sobre polinómios introduzida na Ficha 3, onde um polinómio era representado por uma lista 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. Redefina as funções pedidas nessa ficha, usando agora funções de ordem superior (definidas no `Prelude` ou no `Data.List`) em vez de recursividade explícita:

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

selgrau :: Int -> Polinomio -> Polinomio
selgrau n p = filter (\x -> snd x == n) p

b) `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 n p = length $ selgrau n p

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

grau :: Polinomio -> Int
grau p = maximum $ map snd p

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

deriv :: Polinomio -> Polinomio
deriv p = map (\(c,g) -> (c * fromIntegral g, g - 1)) $ filter (\(c,g) -> g /= 0) p

deriv' :: Polinomio -> Polinomio
deriv' p = [ (c * fromIntegral g, g - 1) | (c,g) <- p, g /= 0]

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

calcula :: Float -> Polinomio -> Float
calcula x p = foldl (\acc (c,g) -> acc + c * x ^ g) 0 p

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

simp :: Polinomio -> Polinomio
simp = filter (\(c,g) -> c /= 0)

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 (cm,gm) = map (\(c,g) -> (cm*c,gm+g))

h) `ordena :: Polinomio -> Polinomio` que ordena um polonómio por ordem crescente dos graus dos seus monómios.

ordena :: Polinomio -> Polinomio
ordena = sortOn snd
-- função sortOn do Data.List

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

normaliza :: Polinomio -> Polinomio
normaliza p = map (foldl (\(cacc,gacc) (c,g) -> (cacc+c,g)) (0,0)) $ groupBy (\m1 m2 -> snd m1 == snd m2) $ ordena p
-- função groupBy do Data.List

normaliza' :: Polinomio -> Polinomio
normaliza' [] = []
normaliza' ((c,g):t) = (c + sum (map fst same_g), g) : (normaliza' diff_g)
    where (same_g, diff_g) = partition (\m -> snd m == g) t
-- função partition do Data.List

normaliza'' :: Polinomio -> Polinomio
normaliza'' p = foldl (\acc m -> adiciona m acc) [] p
    where adiciona :: Monomio -> Polinomio -> Polinomio
          adiciona m [] = [m]
          adiciona (cm,gm) ((c,g):t) = if gm == g then (cm+c,g) : t else (c,g) : adiciona (cm,gm) t

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

soma :: Polinomio -> Polinomio -> Polinomio
soma p1 p2 = foldl (\acc m -> adiciona m acc) p1 p2
    where adiciona :: Monomio -> Polinomio -> Polinomio
          adiciona m [] = [m]
          adiciona (cm,gm) ((c,g):t) = if gm == g then (cm+c,g) : t else (c,g) : adiciona (cm,gm) t

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

produto :: Polinomio -> Polinomio -> Polinomio
produto p1 p2 = foldl (\acc m -> soma (mult m p2) acc) [] p1

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

equiv :: Polinomio -> Polinomio -> Bool
equiv p1 p2 = null (simp (soma p1 (mult (-1,0) p2)))

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

3) Considere a sequinte definição para representar matrizes:

`type Mat a = [[a]]`

Por exemplo, a matriz (triangular superior)

| 1 2 3 |
| 0 4 5 |
| 0 0 6 |

seria representada por: `[[1,2,3], [0,4,5], [0,0,6]]`.

Defina as seguintes funções sobre matrizes (use, sempre que achar apropriado, funções de ordem superior).

a) `dimOK :: Mat a -> Bool` que testa se uma matriz está bem construída (i.e., se todas as linhas têm a mesma dimensão).

dimOK :: Mat a -> Bool
dimOK = (== 1) . length . nub . map length

b) `dimMat :: Mat a -> (Int,Int)` que calcula a dimensão de uma matriz.

dimMat :: Mat a -> (Int, Int)
dimMat [] = (0,0)
dimMat m = (length m, length (head m))

c) `addMat :: Num a => Mat a -> Mat a -> Mat a` que adiciona duas matrizes.

addMat :: Num a => Mat a -> Mat a -> Mat a
addMat = zipWith (zipWith (+))

d) `transpose :: Mat a -> Mat a` que calcula a transposta de uma matriz.

transpose :: Mat a -> Mat a
transpose m = [ map (!! i) m |  i <- [0..c-1]]
    where (l,c) = dimMat m

-- NOTA: existe uma função `transpose` no Data.List que faz a mesma coisa que esta

e) `multMat :: Num a => Mat a -> Mat a -> Mat a` que calcula o produto de duas matrizes.

multMat :: Num a => Mat a -> Mat a -> Mat a
multMat m1 m2 = map (\l -> [ sum (zipWith (*) l [ x !! i | x <- m2 ]) | i <- [0..c-1] ]) m1
    where (l,_) = dimMat m1
          (_,c) = dimMat m2

f) `zipWMat :: (a -> b -> c) -> Mat a -> Mat b -> Mat c` que, à semelhança do que acontece com a função zipWith, combina duas matrizes. Use essa função para definir uma função que adiciona duas matrizes.

zipWMat :: (a -> b -> c) -> Mat a -> Mat b -> Mat c
zipWMat = zipWith . zipWith

addMat' :: Num a => Mat a -> Mat a -> Mat a
addMat' = zipWMat (+)

g) `triSup :: (Num a, Eq a) => Mat a -> Bool` que testa se uma matriz quadrada é triangular superior (i.e., todos os elementos abaixo da diagonal são nulos).

triSup :: (Num a, Eq a) => Mat a -> Bool
triSup m = and [ all (== 0) [ m !! i !! j | j <- [0..i-1] ] | i <- [0..length m - 1]]

h) `rotateLeft :: Mat a -> Mat a` que roda uma matriz 90º para a esquerda. Por exemplo, o resultado de rodar a matriz acima apresentada deve corresponder à matriz:

| 3 5 6 |
| 2 4 0 |
| 1 0 0 |

rotateLeft :: Mat a -> Mat a
rotateLeft m = [ map (!! i) m | i <- [c-1,c-2..0]] 
    where (l,c) = dimMat m

Ficha 5: Funções de ordem superior

1) Apresente definições das seguintes funções de ordem superior, já pré-definidas no Prelude ou no Data.List:

a) any :: (a -> Bool) -> [a] -> Bool que testa se um predicado é verdade para algum elemento de uma lista; por exemplo: any odd [1..10] == True.

b) zipWith :: (a->b->c) -> [a] -> [b] -> [c] que combina os elementos de duas listas usando uma função específica; por exemplo: zipWith (+) [1,2,3,4,5] [10,20,30,40] == [11,22,33,44].

c) takeWhile :: (a->Bool) -> [a] -> [a] que determina os primeiros elementos da lista que satisfazem um dado predicado; por exemplo: takeWhile odd [1,3,4,5,6,6] == [1,3].

d) dropWhile :: (a->Bool) -> [a] -> [a] que elimina os primeiros elementos da lista que satisfazem um dado predicado; por exemplo: dropWhile odd [1,3,4,5,6,6] == [4,5,6,6].

e) span :: (a-> Bool) -> [a] -> ([a],[a]) que calcula simultaneamente os dois resultados anteriores. Note que apesar de poder ser definida à custa das outras duas, usando a definição:

span p l = (takeWhile p l, dropWhile p l)

nessa definição há trabalho redundante que pode ser evitado. Apresente uma definição alternativa onde não haja duplicação de trabalho.

f) deleteBy :: (a -> a -> Bool) -> a -> [a] -> [a] que apaga o primeiro elemento de uma lista que é “igual” a um dado elemento de acordo com a função de comparação que é passada como parâmetro. Por exemplo: deleteBy (\x y -> snd x == snd y) (1,2) [(3,3),(2,2),(4,2)] == [(3,3),(4,2)].

g) sortOn :: Ord b => (a -> b) -> [a] -> [a] que ordena uma lista comparando os resultados de aplicar uma função de extração de uma chave a cada elemento de uma lista. Por exemplo: sortOn fst [(3,1),(1,2),(2,5)] == [(1,2),(2,5),(3,1)].

2) Relembre a questão sobre polinómios introduzida na Ficha 3, onde um polinómio era representado por uma lista de monómios representados por pares (coeficiente, expoente)

Por exemplo, [(2,3), (3,4), (5,3), (4,5)] representa o polinómio 2x^3 + 3x^4 + 5x^3 + 4x^5. Redefina as funções pedidas nessa ficha, usando agora funções de ordem superior (definidas no Prelude ou no Data.List) em vez de recursividade explícita:

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

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

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

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

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

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

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

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

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

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

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

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

3) Considere a sequinte definição para representar matrizes:

type Mat a = [[a]]

Por exemplo, a matriz (triangular superior)

seria representada por: [[1,2,3], [0,4,5], [0,0,6]].

Defina as seguintes funções sobre matrizes (use, sempre que achar apropriado, funções de ordem superior).

a) dimOK :: Mat a -> Bool que testa se uma matriz está bem construída (i.e., se todas as linhas têm a mesma dimensão).

b) dimMat :: Mat a -> (Int,Int) que calcula a dimensão de uma matriz.

c) addMat :: Num a => Mat a -> Mat a -> Mat a que adiciona duas matrizes.

d) transpose :: Mat a -> Mat a que calcula a transposta de uma matriz.

e) multMat :: Num a => Mat a -> Mat a -> Mat a que calcula o produto de duas matrizes.

f) zipWMat :: (a -> b -> c) -> Mat a -> Mat b -> Mat c que, à semelhança do que acontece com a função zipWith, combina duas matrizes. Use essa função para definir uma função que adiciona duas matrizes.

g) triSup :: (Num a, Eq a) => Mat a -> Bool que testa se uma matriz quadrada é triangular superior (i.e., todos os elementos abaixo da diagonal são nulos).

h) rotateLeft :: Mat a -> Mat a que roda uma matriz 90º para a esquerda. Por exemplo, o resultado de rodar a matriz acima apresentada deve corresponder à matriz:

1) Apresente definições das seguintes funções de ordem superior, já pré-definidas no `Prelude` ou no `Data.List`:

a) `any :: (a -> Bool) -> [a] -> Bool` que testa se um predicado é verdade para algum elemento de uma lista; por exemplo: `any odd [1..10] == True`.

b) `zipWith :: (a->b->c) -> [a] -> [b] -> [c]` que combina os elementos de duas listas usando uma função específica; por exemplo: `zipWith (+) [1,2,3,4,5] [10,20,30,40] == [11,22,33,44]`.

c) `takeWhile :: (a->Bool) -> [a] -> [a]` que determina os primeiros elementos da lista que satisfazem um dado predicado; por exemplo: `takeWhile odd [1,3,4,5,6,6] == [1,3]`.

d) `dropWhile :: (a->Bool) -> [a] -> [a]` que elimina os primeiros elementos da lista que satisfazem um dado predicado; por exemplo: `dropWhile odd [1,3,4,5,6,6] == [4,5,6,6]`.

e) `span :: (a-> Bool) -> [a] -> ([a],[a])` que calcula simultaneamente os dois resultados anteriores. Note que apesar de poder ser definida à custa das outras duas, usando a definição:

`span p l = (takeWhile p l, dropWhile p l)`

f) `deleteBy :: (a -> a -> Bool) -> a -> [a] -> [a]` que apaga o primeiro elemento de uma lista que é “igual” a um dado elemento de acordo com a função de comparação que é passada como parâmetro. Por exemplo: `deleteBy (\x y -> snd x == snd y) (1,2) [(3,3),(2,2),(4,2)] == [(3,3),(4,2)]`.

g) `sortOn :: Ord b => (a -> b) -> [a] -> [a]` que ordena uma lista comparando os resultados de aplicar uma função de extração de uma chave a cada elemento de uma lista. Por exemplo: `sortOn fst [(3,1),(1,2),(2,5)] == [(1,2),(2,5),(3,1)]`.

Por exemplo, `[(2,3), (3,4), (5,3), (4,5)]` representa o polinómio 2x^3 + 3x^4 + 5x^3 + 4x^5. Redefina as funções pedidas nessa ficha, usando agora funções de ordem superior (definidas no `Prelude` ou no `Data.List`) em vez de recursividade explícita:

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

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

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

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

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

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

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

h) `ordena :: Polinomio -> Polinomio` que ordena um polonómio por ordem crescente dos graus dos seus monómios.

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

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

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

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

`type Mat a = [[a]]`

seria representada por: `[[1,2,3], [0,4,5], [0,0,6]]`.

a) `dimOK :: Mat a -> Bool` que testa se uma matriz está bem construída (i.e., se todas as linhas têm a mesma dimensão).

b) `dimMat :: Mat a -> (Int,Int)` que calcula a dimensão de uma matriz.

c) `addMat :: Num a => Mat a -> Mat a -> Mat a` que adiciona duas matrizes.

d) `transpose :: Mat a -> Mat a` que calcula a transposta de uma matriz.

e) `multMat :: Num a => Mat a -> Mat a -> Mat a` que calcula o produto de duas matrizes.

f) `zipWMat :: (a -> b -> c) -> Mat a -> Mat b -> Mat c` que, à semelhança do que acontece com a função zipWith, combina duas matrizes. Use essa função para definir uma função que adiciona duas matrizes.

g) `triSup :: (Num a, Eq a) => Mat a -> Bool` que testa se uma matriz quadrada é triangular superior (i.e., todos os elementos abaixo da diagonal são nulos).

h) `rotateLeft :: Mat a -> Mat a` que roda uma matriz 90º para a esquerda. Por exemplo, o resultado de rodar a matriz acima apresentada deve corresponder à matriz: