Я пытаюсь определить функцию, которая удалит дубликаты из списка. Пока у меня есть рабочая реализация:
rmdups :: Eq a => [a] -> [a]
rmdups [] = []
rmdups (x:xs) | x `elem` xs = rmdups xs
| otherwise = x : rmdups xs
Однако я хотел бы переработать это без использования elem. Какой был бы лучший способ для этого?
Я хотел бы сделать это, используя мою собственную функцию, а не nub или nubBy.
Я не думаю, что вы сможете сделать это без 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]) []
Оба кода и 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 b a
then rmdups' a c
else b : rmdups' (Set.insert b a) c
Как вы можете видеть, результаты тестов доказывают, что это решение является наиболее эффективным. Здесь вы можете найти источник этого эталона .
Использование 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
Хотя это, безусловно, более продвинутый, я думаю, что он довольно изящный и демонстрирует некоторые полезные парадигмы функционального программирования.
... или используя объединение функций из Data.List, применяемое к самому себе:
import Data.List
unique x = union x x
Слишком поздно ответить на этот вопрос, но я хочу поделиться своим оригинальным решением без использования 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-п"
Если вы хотите взять первый и не последний дублирующие элементы списка, как вы пытаетесь сделать, просто изменить take на drop в функции и изменить нумерацию zip [0..] на zip [1..].