Questão 43: constroiMSet
Voltar
Considere que se usa o tipo [(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 constroiMSet :: Ord a => [a] -> [(a,Int)] que, dada uma lista ordenada por ordem crescente, calcula o multi-conjunto dos seus elementos.
Exemplo
> constroiMSet "aaabccc"
[(’a’,3), (’b’,1), (’c’,3)]Resolução
constroiMSet :: Ord a => [a] -> [(a,Int)]
constroiMSet [] = []
constroiMSet (l:ls) = insereMSet l (constroiMSet ls)Explicação
Tal como na função nub de uma das questões anteriores, nesta função, dependendo da direção na qual se percorre a lista, a ordem dos elementos no resultado será diferente. Esta resolução é a mais simples, mas o resultado difere do exemplo, em termos de ordem dos elementos. Apesar do enunciado não especificar este pormenor, pode haver quem prefira ter uma função que respeite a 100% o exemplo, logo, deixo também uma resolução alternativa com um acumulador e que já produz uma lista igual à do exemplo.
Resolução
constroiMSet [] = []
constroiMSet (h:t) = constroiMSetAux t [h]
constroiMSetAux [] acc = [(head acc, length acc)]
constroiMSetAux (h:t) acc
| h `elem` acc = constroiMSetAux t (h:acc)
| otherwise = (head acc, length acc) : constroiMSetAux t [h]