string para multi conjunto

[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 January 30, 2016 at 09:29 PM by pwseo
tags code, syntax highlight

[pwseo]

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ê?

[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 January 30, 2016 at 11:04 PM by pwseo
indent, syntax highlight.

[pwseo]

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

[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