Jump to content

string para multi conjunto


miguelsilva94
 Share

Recommended Posts

miguelsilva94

Porque é que ele mete à cabeça da lista o elemento que mais vezes ocorre? como poderei solucionar isto?

obrigado

type MSet a = [(a , Int)]

converte :: Eq a => [a] -> MSet a
converte [] = []
converte (x:xs) = insere x (converte xs)

insere:: Eq a => a -> MSet a -> [(a,Int)]
insere x [] = [(x,1)]
insere x ((x1,y1):xs) | x == x1 = [(x1,(y1+1))] ++ xs
                     | otherwise = [(x1,y1)] ++ insere x xs

o objetivo era devolver.

*Main> converte "bacaba"
[('b',2),('a',3),('c',1)]

no entanto devolve:

*Main> converte "bacaba"
[('a',3),('b',2),('c',1)]
Edited by pwseo
tags code, syntax highlight
Link to comment
Share on other sites

Porque é que ele mete à cabeça da lista o elemento que mais vezes ocorre? como poderei solucionar isto?

obrigado

Isso não é bem o que acontece, repara:

*Main> converte "aaaab"
[('b',1),('a',4)]

Consegues perceber porquê?

Link to comment
Share on other sites

miguelsilva94

Isso não é bem o que acontece, repara:

*Main> converte "aaaab"
[('b',1),('a',4)]

Consegues perceber porquê?

Não.

Acho que nunca poderá funcionar porque da maneira que fiz não comecei por pegar no primeiro elemento da string e devia tê-lo feito. Deveria ser algo do género. mas mesmo este não funciona porque me dá o que quero mais alguma coisa. devo esquecer esta nova tentativa ou voltar a tentar da maneira como estava a fazer? e o que poderei fazer para arranjar a nova tentativa?

converte :: Eq a => [a] -> MSet a
converte [] = []
converte (x:xs) = (x,1+quantos x xs) : converte xs
 where quantos x [] = 0
       quantos x (y:ys) = if (x == y) then 1 + quantos x ys else quantos x ys
Edited by pwseo
indent, syntax highlight.
Link to comment
Share on other sites

Calma 🙂

O problema na tua versão anterior era o facto de adicionares novos elementos ao início da lista:

converte (x:xs) = insere x (converte xs)

ou seja:

insere 'b' (converte "acaba")
insere 'b' (insere 'a' (converte "caba"))
insere 'b' (insere 'a' (insere 'c' (converte "aba")))
insere 'b' (insere 'a' (insere 'c' (insere 'a' (converte "ba"))))
insere 'b' (insere 'a' (insere 'c' (insere 'a' (insere 'b' (converte "a")))))
insere 'b' (insere 'a' (insere 'c' (insere 'a' (insere 'b' (insere 'a' [])))))
insere 'b' (insere 'a' (insere 'c' (insere 'a' (insere 'b' [('a', 1)]))))
insere 'b' (insere 'a' (insere 'c' (insere 'a' [('a', 1), ('b', 1)])))
insere 'b' (insere 'a' (insere 'c' [('a', 2), ('b', 1)]))
insere 'b' (insere 'a' [('a', 2), ('b', 1), ('c', 1)])
insere 'b' [('a', 3), ('b', 1), ('c', 1)]
[('a', 3), ('b', 2), ('c', 1)]

Como podes ver, o problema é a ordem pela qual fazes as operações; a primeira letra da string é a última a ser «inserida».

O que tu procuras é que a função insere seja invocada com cada letra da string e o seu resultado utilizado como segundo argumento para a invocação seguinte... essencialmente uma left fold (foldl):

converte :: Eq a => [a] -> MSet a
converte = foldl (flip insere) []
-- precisamos do flip porque para a 'insere' functionar com a 'foldl' é necessário
-- (neste caso) invertermos a ordem pela qual aceita os argumentos
-- Alternativamente, podes simplesmente modificar a 'insere' directamente para aceitar
-- os argumentos pela ordem inversa

insere:: Eq a => a -> MSet a -> [(a,Int)] -- aqui podes usar 'MSet a' em vez de [(a, Int)]
insere x [] = [(x,1)]
insere x ((x1,y1):xs) | x == x1 = [(x1,(y1+1))] ++ xs
                     | otherwise = [(x1,y1)] ++ insere x xs
Link to comment
Share on other sites

miguelsilva94

sim percebe-se muito bem pelo exemplo que deste. eu ainda cheguei a tentar com o flip e reverse mas não correu muito bem, daí ter avançado para a segunda tentativa. obrigado mais uma vez pela explicação. entretanto consegui perceber o que estava a falhar na nova tentativa: aquilo estava a chamar a converte recursivamente pelo que estava a calcular a quantidade de caracteres que ja tinham sido calculados.

converte :: Eq a => [a] -> MSet a
converte [] = []
converte (x:xs) = (x,1+quantos x xs) : converte (filter (/= x) xs)
 where quantos x [] = 0
       quantos x (y:ys) = if (x == y) then 1 + quantos x ys else quantos x ys
Link to comment
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
 Share

×
×
  • 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.