2

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.

2 Respostas 2

6

Estou a assumir que este é o output que desejas.

  • aaabbbcddd → abcd
  • aaabbbaaacddd → abacd

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:

  • Se dois elementos adjacentes são iguais então salta o primeiro dos dois elementos e avalia de forma recursiva o resto da lista até encontrar dois elementos diferentes ou encontrar um dos casos triviais.
  • Caso sejam diferentes então inclui o primeiro elemento na lista resultado e avalia o resto da lista de forma recursiva.

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:

  • aaabbbaaacddd → abcd

Então basta ordenar a lista (usando a função sort) antes de executares a função removeDups.

3

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"
2
  • 2
    Resolve o problema, mas veja que é uma implementação quadrática (O(n^2)), para cada elemento você percorre a lista toda olhando se ele não está lá, praticamente um bubble sort da remoção de duplicatas (mas vai um upvote pela simplicidade da função).
    – BrunoRB
    Commented 25/02/2016 às 20:37
  • Verdade, mas me parece que não tem muito o que fazer. O nub (método que faz a mesma coisa) do Data.List faz algo muito parecido. hackage.haskell.org/package/base-4.8.2.0/docs/src/…
    – Rigotti
    Commented 26/02/2016 às 20:43

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .