Удаление дубликатов из списка в Haskell

Ответ 1

Я не думаю, что вы сможете сделать это без elem (или вашей собственной повторной реализации).

Однако с вашей реализацией существует семантическая проблема. Когда элементы дублируются, вы сохраняете последний. Лично я ожидаю, что он сохранит первый дубликат и оставит остальные.

*Main> rmdups "abacd"
"bacd"

Решение состоит в том, чтобы нарезать "видимые" элементы через переменную состояния.

removeDuplicates :: Eq a => [a] -> [a]
removeDuplicates = rdHelper []
    where rdHelper seen [] = seen
          rdHelper seen (x:xs)
              | x `elem` seen = rdHelper seen xs
              | otherwise = rdHelper (seen ++ [x]) xs

Это больше или меньше, чем nub реализовано в стандартной библиотеке (читайте источник здесь). Небольшая разница в реализации nub гарантирует, что она non-strict, а removeDuplicates выше строго (она возвращает весь список перед возвратом).

Примитивная рекурсия на самом деле переполнена здесь, если вас не беспокоит строгость. removeDuplicates может быть реализована в одной строке с помощью foldl:

removeDuplicates2 = foldl (\seen x -> if x `elem` seen
                                      then seen
                                      else seen ++ [x]) []

Ответ 2

Оба кода и nub имеют сложность O(N^2).

Вы можете улучшить сложность O(N log N) и не использовать elem путем сортировки, группировки и принятия только первого элемента каждой группы.

Концептуально,

rmdups :: (Ord a) => [a] -> [a]
rmdups = map head . group . sort

Предположим, вы начинаете со списка [1, 2, 1, 3, 2, 4]. Сортируя его, вы получите [1, 1, 2, 2, 3, 4]; сгруппировав это, вы получите [[1, 1], [2, 2], [3], [4]]; наконец, взяв главу каждого списка, вы получите [1, 2, 3, 4].

Полная реализация вышеуказанного просто включает в себя расширение каждой функции.

Обратите внимание, что для этого требуется более сильное ограничение Ord для элементов списка, а также изменение их порядка в возвращенном списке.

Ответ 3

Еще проще.

import Data.Set 
mkUniq :: Ord a => [a] -> [a]
mkUniq = toList . fromList

Преобразование набора в список элементов в O (n) времени:

toList :: Set a -> [a]

Создайте набор из списка элементов в O (n log n) времени:

fromList :: Ord a => [a] -> Set a

В python это ничем не отличается.

def mkUniq(x): 
   return list(set(x)))

Ответ 4

То же, что и решение @scvalex, имеет сложность O(n * log n) и зависимость Ord. В отличии от него он сохраняет порядок, сохраняя первые вхождения элементов.

import qualified Data.Set as Set

rmdups :: Ord a => [a] -> [a]
rmdups = rmdups' Set.empty where
  rmdups' _ [] = []
  rmdups' a (b : c) = if Set.member b a
    then rmdups' a c
    else b : rmdups' (Set.insert b a) c

Результаты тестов

Как вы можете видеть, результаты тестов доказывают, что это решение является наиболее эффективным. Здесь вы можете найти источник этого эталона .

Ответ 5

Использование recursion-schemes:

import Data.Functor.Foldable

dedup :: (Eq a) => [a] -> [a]
dedup = para pseudoalgebra
    where pseudoalgebra Nil                 = []
          pseudoalgebra (Cons x (past, xs)) = if x `elem` past then xs else x:xs

Хотя это, безусловно, более продвинутый, я думаю, что он довольно изящный и демонстрирует некоторые полезные парадигмы функционального программирования.

Ответ 6

... или используя объединение функций из Data.List, применяемое к самому себе:

import Data.List

unique x = union x x

Ответ 7

Слишком поздно ответить на этот вопрос, но я хочу поделиться своим оригинальным решением без использования elem и не предполагать Ord.

rmdups' :: (Eq a) => [a] -> [a]
rmdups' [] = []
rmdups' [x] = [x]
rmdups' (x:xs) = x : [ k  | k <- rmdups'(xs), k /=x ]

Это решение удаляет дубликаты в конце ввода, в то время как реализация вопроса удаляется в начале. Например,

rmdups "maximum-minimum"
-- "ax-nium"

rmdups' "maximum-minimum"
-- ""maxiu-n"

Кроме того, эта сложность кода - O (N * K), где N - длина строки, а K - количество уникальных символов в строке. N >= K, таким образом, это будет O (N ^ 2) в худшем случае, но это означает, что в строке нет повторения, и это не похоже на то, что вы пытаетесь удалить дубликаты в строке.

Ответ 8

Грэм Хаттон имеет функцию rmdups на p. 86 программирования в Haskell. Он сохраняет порядок. Это так.

rmdups :: Eq a => [a] -> [a]
rmdups [] = []
rmdups (x:xs) = x : filter (/= x) (rmdups xs)
rmdups "maximum-minimum"

"Maxiu-п"

Это беспокоило меня, пока я не увидел функцию Хаттона. Затем я снова попытался. Есть две версии: первая хранит последний дубликат, второй - первый.

rmdups ls = [d|(z,d)<- zip [0..] ls, notElem d $ take z ls]
rmdups "maximum-minimum"

"Maxiu-п"

Если вы хотите взять первый и не последний дублирующие элементы списка, как вы пытаетесь сделать, просто изменить take на drop в функции и изменить нумерацию zip [0..] на zip [1..].