Considere que se usa o tipo type MSet a = [(a,Int)] para representar multi-conjuntos de elementos de a. Considere ainda que nestas listas não há pares cuja primeira componente
coincida, nem cuja segunda componente seja menor ou igual a zero.
Defina a função converteMSet :: MSet a -> [a] que converte um multi-conjunto na lista dos seus elementos. Por exemplo, converteMSet [('b',2), ('a',4), ('c',1)] corresponde a "bbaaaac".
<aside> 📝 Resolução:
replicate):converteMSet :: MSet a -> [a]
converteMSet [] = []
converteMSet ((e,n):t) = replicate n e ++ converteMSet t
converteMSet' :: MSet a -> [a]
converteMSet' [] = []
converteMSet' ((e,n):t)
| n == 0 = converteMSet' t
| otherwise = e : converteMSet' ((e,n-1) : t)
</aside>
Defina a função removeMSet :: Eq a => a -> MSet a -> MSet a que remove um elemento a um multi-conjunto. Se o elemento não existir, deve ser retornado o multi-conjunto recebido.
Por exemplo, removeMSet 'c' [('b',2), ('a',4), ('c',1)] corresponde a [('b',2), ('a',4)], e removeMSet 'a' [('b',2), ('a',4), ('c',1)] corresponde a [('b',2), ('a',3), ('c',1)].
<aside> 📝 Resolução:
removeMSet :: Eq a => a -> MSet a -> MSet a
removeMSet _ [] = []
removeMSet a ((e,n):t)
| a == e && n > 0 = (e,n-1) : t
| a == e = t
| otherwise = (e,n) : removeMSet a t
</aside>
Defina a função uniaoMSet :: Eq a => MSet a -> MSet a -> MSet a que faz a união de dois multi-conjuntos.
Por exemplo, uniaoMSet [('b',2),('a',4),('c',1)] [('c',7),('a',3),('d',5)] corresponde a [('c',8),('a',7),('d',5),('b',2)].
<aside> 📝 Resolução:
uniaoMSet :: Eq a => MSet a -> MSet a -> MSet a
uniaoMSet l1 l2 = foldr insereMSet l1 l2
insereMSet :: Eq a => (a, Int) -> MSet a -> MSet a
insereMSet a [] = [a]
insereMSet (x,y) ((e,n):t)
| x == e = (e,n+y) : t
| otherwise = (e,n) : insereMSet (x,y) t
O objetivo nesta alínea é gerar uma lista equivalente à união das duas listas dadas. A forma mais simples de o fazer é simplesmente inserir os elementos de uma das listas na outra. Depois de definir uma função insereMSet, que insere um elemento num MSet, apenas é preciso chamar essa função para as duas listas dadas. Isto pode ser feito recursivamente ou usando um fold, tal como na resolução acima, onde inserimos os elementos de l2 em l1 (o acumulador).
</aside>
Considere o seguinte tipo usado para descrever movimentos de um robot e a sua posição numa grelha.
type Posicao = (Int,Int)
data Movimento = Norte | Sul | Este | Oeste
data Caminho = C Posicao [Movimento]
Defina uma instância da classe Eq para o tipo Caminho, considerando iguais os caminhos com a mesma posição de partida e de chegada e com o mesmo número de movimentos.
<aside> 📝 Resolução:
instance Eq Caminho where
(==) :: Caminho -> Caminho -> Bool
C pos1 movs1 == C pos2 movs2 =
pos1 == pos2
&& length movs1 == length movs2
&& posFinal pos1 movs1 == posFinal pos2 movs2
posFinal :: Posicao -> [Movimento] -> Posicao
posFinal pos movs = foldl (\\(x,y) mov ->
case mov of
Norte -> (x,y-1)
Sul -> (x,y+1)
Este -> (x+1,y)
Oeste -> (x-1,y)
) pos movs
Para este exercício, apenas era preciso definir a função (==). As condições para esta função ser verdadeira eram dadas no enunciado. Comparar as posições iniciais e os números de movimentos é trivial. O único desafio aqui era comparar as posições de chegada, mas isso poderia ser feito facilmente com recurso a uma função auxiliar que calcula estes valores. Tal como no exercício anterior, esta função podia ser definida recursivamente ou com um fold.
</aside>
Apresente uma definição alternativa da função func, usando recursividade explícita em vez de funções de ordem superior e fazendo uma única travessia da lista.
func :: [[Int]] -> [Int]
func l = concat (filter (\\x -> sum x > 10) l)
<aside> 📝 Resolução:
Para este exercício, antes de o resolver, é importante determinar o que é a função original faz. Na função original, temos uma lista de listas l. Esta lista é filtrada, usando uma função que determina se a soma de cada sub-lista é superior a 10. Depois de filtrada, a lista é concatenada, ou seja, as suas sub-listas são agrupadas numa só. Assim, podemos definir um exemplo como este: func [[1,2,3],[4,5,6],[7,8,9]] = [4,5,6,7,8,9], equivalente à concatenação das sub-listas na lista original cuja soma dos elementos é superior a 10.
Depois de efetuar este passo, torna-se bastante mais simples definir uma função recursiva que faça o mesmo que a função func. Podemos usar a função sum na mesma para calcular a soma de cada sub-lista. Caso esta seja superior a 10, concatenamos a sub-lista h ao resto da lista final (i.e., ao resultado da chamada recursiva), usando a função (++).
func' :: [[Int]] -> [Int]
func' [] = []
func' (h:t)
| sum h > 10 = h ++ func' t
| otherwise = func' t
</aside>