Jump to content

Número de ocorrências numa lista


maierlly oliveira

Recommended Posts

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.

Link to post
Share on other sites
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
  • Vote 1
Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.