## Recommended Posts

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

```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
##### Share on other sites

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

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

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

Consegues perceber porquê?

##### Share on other sites

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.
##### 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
```
##### Share on other sites

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
```

## Create an account

Register a new account

×

• #### Revista PROGRAMAR

• Wiki
• IRC
×
• Create New...