уникальные элементы в списке haskell
хорошо, это, вероятно, будет во вводной части, но: существует ли стандартная библиотечная функция для нахождения уникальных элементов в списке? мой (ре) реализация, для разъяснения:
has :: (Eq a) => [a] -> a -> Bool
has [] _ = False
has (x:xs) a
| x == a = True
| otherwise = has xs a
unique :: (Eq a) => [a] -> [a]
unique [] = []
unique (x:xs)
| has xs x = unique xs
| otherwise = x : unique xs
2 ответа
Функция nub из Data.List (нет, на самом деле ее нет в прелюдии) определенно делает что-то вроде того, что вы хотите, но это не совсем то же самое, что ваша уникальная функция. Они оба сохраняют первоначальный порядок элементов, но unique сохраняет последний.
вхождение каждого элемента, в то время как nub сохраняет первое вхождение.
Вы можете сделать это, чтобы заставить nub действовать точно так же, как unique, если это важно (хотя у меня есть ощущение, что это не так):
unique = reverse . nub . reverse
Кроме того, nub хорош только для небольших списков.
Его сложность квадратична, поэтому он начинает работать медленно, если ваш список может содержать сотни элементов.
Если ограничить типы типами, имеющими экземпляр Ord, можно улучшить его масштабирование.
Эта вариация на nub по-прежнему сохраняет порядок элементов списка, но ее сложность O(n * log n):
import qualified Data.Set as Set
nubOrd :: Ord a => [a] -> [a]
nubOrd xs = go Set.empty xs where
go s (x:xs)
| x `Set.member` s = go s xs
| otherwise = x : go (Set.insert x s) xs
go _ _ = []
На самом деле, было предложено добавить nubOrd к Data.Set.
Я искал (Eq a) => [a] -> [a] в Hoogle .
Первым результатом был кусок (удаление повторяющихся элементов из списка).
Google - это круто.