Definir uma função recursiva primitiva capaz de comprimir a lista removendo todos os elementos repetidos em sequencia. Ex : aaabbbcddd → abcd
Alguma ideia de como fazer isso? Sinceramente não sei por onde começar.
Estou a assumir que este é o output que desejas.
Para isso podes tentar algo do género.
Versão 1:
removeDups :: (Eq a) => [a] -> [a]
removeDups [] = []
removeDups (xs : []) = [xs]
removeDups (x1:x2:xs)
| x1 == x2 = removeDups (x2 : xs)
| otherwise = x1 : removeDups (x2 : xs)
Os seguintes casos são triviais.
removeDups [] = [] -- Lista vazia
removeDups (xs : []) = [xs] -- Lista apenas com um elemento
A lógica para os outros casos é a seguinte:
Versão 2:
Alternativa que usa apenas funções pré-definidas
removeDups :: (Eq a) => [a] -> [a]
removeDups= map head . group
Esta versão usa a função group
que recebe como parâmetro uma lista e devolve uma lista de listas em que cada uma das sub-listas é composta apenas por elementos iguais.
Função group
group "Mississippi" = ["M","i","ss","i","ss","i","pp","i"]
Depois é simples, aplicas a função head
a cada uma das sublistas para devolver apenas o primeiro elemento.
Caso desejes obter uma lista sem elementos repetidos:
Então basta ordenar a lista (usando a função sort
) antes de executares a função removeDups
.
Já faz um certo tempo que foi perguntado, mas aí vai a minha implementação.
removeDup :: String -> String
removeDup [] = []
removeDup [a] = [a]
removeDup (x:xs) = x:(removeDup $ filter (/=x) xs)
Basicamente a mágica acontece quando o filter remove os elementos x de xs
removeDup "abacabc"
-- 1º passo => 'a' : "bcbc"
-- 2º passo => 'a' : 'b' : "cc"
-- 3º passo => 'a' : 'b' : 'c' : [] == "abc"