В порядке, это, вероятно, будет в прелюдии, но: есть ли стандартная библиотечная функция для поиска уникальных элементов в списке? моя (повторная) реализация, для уточнения, заключается в следующем:
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
Функция nub из Data.List (нет, она на самом деле не в Prelude) определенно делает что-то вроде того, что вы хотите, но это не совсем то же самое, что и ваша функция unique. Они сохраняют первоначальный порядок элементов, но 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.
Первый результат был nub (удалите повторяющиеся элементы из списка).
Hoogle потрясающий.
import Data.Set (toList, fromList)
uniquify lst = toList $ fromList lst
Я думаю, что уникальный должен возвращать список элементов, которые появляются только один раз в исходном списке; то есть любые элементы исходного списка, которые появляются более одного раза, не должны включаться в результат.
Можно предложить альтернативное определение, unique_alt:
unique_alt :: [Int] -> [Int]
unique_alt [] = []
unique_alt (x:xs)
| elem x ( unique_alt xs ) = [ y | y <- ( unique_alt xs ), y /= x ]
| otherwise = x : ( unique_alt xs )
Вот несколько примеров, которые подчеркивают различия между unique_alt и unqiue:
unique [1,2,1] = [2,1]
unique_alt [1,2,1] = [2]
unique [1,2,1,2] = [1,2]
unique_alt [1,2,1,2] = []
unique [4,2,1,3,2,3] = [4,1,2,3]
unique_alt [4,2,1,3,2,3] = [4,1]
Алгоритм в Haskell для создания уникального списка:
data Foo = Foo { id_ :: Int
, name_ :: String
} deriving (Show)
alldata = [ Foo 1 "Name"
, Foo 2 "Name"
, Foo 3 "Karl"
, Foo 4 "Karl"
, Foo 5 "Karl"
, Foo 7 "Tim"
, Foo 8 "Tim"
, Foo 9 "Gaby"
, Foo 9 "Name"
]
isolate :: [Foo] -> [Foo]
isolate [] = []
isolate (x:xs) = (fst f) : isolate (snd f)
where
f = foldl helper (x,[]) xs
helper (a,b) y = if name_ x == name_ y
then if id_ x >= id_ y
then (x,b)
else (y,b)
else (a,y:b)
main :: IO ()
main = mapM_ (putStrLn . show) (isolate alldata)
Вывод:
Foo {id_ = 9, name_ = "Name"}
Foo {id_ = 9, name_ = "Gaby"}
Foo {id_ = 5, name_ = "Karl"}
Foo {id_ = 8, name_ = "Tim"}
Другой способ удаления дубликатов:
unique :: [Int] -> [Int]
unique xs = [x | (x,y) <- zip xs [0..], x `notElem` (take y xs)]