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

Я не думаю, что вы сможете сделать это без 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 гарантирует, что она не является строгой , а removeDuplicates выше является строгой (она возвращает весь список перед возвратом).

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

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

Оба кода и 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 для элементов списка, а также изменение их порядка в возвращаемом списке.

Еще проще.

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

То же, что и решение @ 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 ba then rmdups' ac else b : rmdups' (Set.insert ba) c 

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

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

Использование рекуррентных схем :

 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 

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

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

 import Data.List unique x = union xx 

Слишком поздно ответить на этот вопрос, но я хочу поделиться своим решением, которое оригинально, не используя 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) в худшем случае, но это означает, что в строке нет повторения, и это не похоже на то, что вы пытаетесь удалить дубликаты в строке.

Грэм Хаттон имеет функцию 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-п"

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