Número de ocorrências numa lista

[maierlly oliveira]

olá!! Sou iniciante na linguagem Haskell e pesquisando listas de exercícios para praticar e entender mais me deparei com essa questão:

 Suponha que tenhamos uma lista de inteiros e que desejamos ordenar seus elementos de acordo com suas ocorrências. Isto é, teremos os elementos mais raros posicionados primeiro e os elementos mais frequentes por último.
Exemplos:
[4,4,2,1,3,3,2,4,3,4] -> [1,2,3,4]
[5,3,5,3,5,3,7,1,3,1,3,5] -> [7,1,5,3]

Alguém pode me ajudar a como desenvolver ela.

obs: penso que deva ser criada uma função que compare os elementos da lista verificando quais são iguais(duplicados) e em seguida ordenar pela quantidade de ocorrências, mas não sei estruturar bem essa ideia.

[thoga31]

Deixo aqui um possível algoritmo:

1. Ordenar os elementos da lista;
2. Agrupar os elementos consecutivos que sejam iguais;
3. Formar uma lista de tuplos que indique o elemento e quantos existem;
4. Ordenar esta nova lista pelo número de elementos;
5. Extrair apenas os elementos.

O processamento da segunda lista que mostraste teria os seguintes resultados intermédios:

[5,3,5,3,5,3,7,1,3,1,3,5]
[1,1,3,3,3,3,3,5,5,5,5,7]
[[1,1],[3,3,3,3,3],[5,5,5,5],[7]]
[(2,1),(5,3),(4,5),(1,7)]
[(1,7),(2,1),(4,5),(5,3)]
[7,1,5,3]

Para cada um dos pontos, o Haskell fornece algumas funções úteis, respectivamente:

1. sort;
2. groupBy;
3. map;
4. sortBy;
5. map.

Basta então compor as funções com o operador . a fim de implementar o algoritmo. Isto traduz-se no seguinte código:

import Data.List (sort, sortBy, groupBy)
import Data.Ord (comparing)

sortByFreq :: (Eq a, Ord a) => [a] -> [a]
sortByFreq [] = []
sortByFreq xs = map (snd) . sortBy (comparing fst) . map (\x -> (length x, head x)) . groupBy (==) . sort $ xs

Cumprimentos.

Edited December 12, 2020 at 02:19 AM by thoga31
Pequena gafe no código

[maierlly oliveira]

Ainda não conheço essas funções, vou estudar mais sobre elas. Muito Obrigado pela ajuda 🙂

[pdfrod]

9 hours ago, thoga31 said:

Deixo aqui um possível algoritmo:

1. Ordenar os elementos da lista;
2. Agrupar os elementos consecutivos que sejam iguais;
3. Formar uma lista de tuplos que indique o elemento e quantos existem;
4. Ordenar esta nova lista pelo número de elementos;
5. Extrair apenas os elementos.

O processamento da segunda lista que mostraste teria os seguintes resultados intermédios:

[5,3,5,3,5,3,7,1,3,1,3,5]
[1,1,3,3,3,3,3,5,5,5,5,7]
[[1,1],[3,3,3,3,3],[5,5,5,5],[7]]
[(2,1),(5,3),(4,5),(1,7)]
[(1,7),(2,1),(4,5),(5,3)]
[7,1,5,3]

Para cada um dos pontos, o Haskell fornece algumas funções úteis, respectivamente:

1. sort;
2. groupBy;
3. map;
4. sortBy;
5. map.

Basta então compor as funções com o operador . a fim de implementar o algoritmo. Isto traduz-se no seguinte código:

import Data.List (sort, sortBy, groupBy)
import Data.Ord (comparing)

sortByFreq :: (Eq a, Ord a) => [a] -> [a]
sortByFreq [] = []
sortByFreq xs = map (snd) . sortBy (comparing fst) . map (\x -> (length x, head x)) . groupBy (==) . sort $ xs

Cumprimentos.

Também faria de modo semelhante.

Usando o sortOn (que é uma função que apareceu mais recente no Data.List) dá para simplificar um pouco:

sortByFreq :: (Eq a, Ord a) => [a] -> [a]
sortByFreq xs = map head $ sortOn length $ group $ sort xs