Questão 26: nub

Voltar

Apresente uma definição recursiva da função (pré-definida) nub :: Eq a => [a] -> [a] que calcula uma lista com os mesmos elementos da recebida, sem repetições.

Exemplo

> nub [1,2,1,2,3,1,2]
[1,2,3]

Resolução

Clica para revelar

nub :: Eq a => [a] -> [a]
nub [] = []
nub (h:t) = if h `elem` t 
            then nub t
            else h : nub t

Explicação

Clica para revelar

Esta versão da função funciona e é bastante simples, mas o output produzido é diferente do do exemplo. Por outras palavras, esta função, para o exemplo fornecido, produz a seguinte lista:

> nub [1,2,1,2,3,1,2]
[3,1,2]

Na minha opinião, isto não faz diferença, pois no enunciado não é especificado qual deverá ser a ordem dos elementos da lista resultante, mas quem quiser uma função que devolva uma lista exatamente igual à do exemplo pode consultar a resolução alternativa que usa um acumulador.

Resolução

Clica para revelar

nub :: Eq a => [a] -> [a]
nub l = nubAux l []

nubAux :: Eq a => [a] -> [a] -> [a]
nubAux [] acc = reverse acc
nubAux (h:t) acc
    | h `elem` acc = nubAux t acc
    | otherwise = nubAux t (h : acc)

Explicação

Clica para revelar

Esta versão usa um acumulador para recolher os elementos da lista da esquerda para a direita. Porém, como os elementos são sempre colocados à esquerda do acumulador, a lista final vai estar “invertida”, daí ser feito reverse acc no caso de paragem, para inverter a lista final. Também poderia ser feito acc ++ [h] no caso recursivo, em vez de h : acc, o que também colocaria os elementos na ordem “correta”, mas esta solução é pouco eficiente, devido à forma como as listas são armazenadas em Haskell. É sempre preferível colocar novos elementos à esquerda.

Relembro que a ordem dos elementos na lista final não é relevante, apenas a sua presença.