Удалить дубликаты из списка

Question

У меня есть тип данных:

data SidesType = Sides Int Int Int deriving (Show)

И мне нужна функция, которая получает список SidesType и удаляет из него дубликаты.

*Main> let a = [Sides 3 4 5,Sides 3 4 5,Sides 5 12 13,Sides 6 8 10,Sides 6 8 10,Sides 8 15 17,Sides 9 12 15,Sides 5 12 13,Sides 9 12 15,Sides 12 16 20,Sides 8 15 17,Sides 15 20 25,Sides 12 16 20,Sides 15 20 25]
*Main> removeDuplicateFromList [] a
[Sides 3 4 5,Sides 5 12 13,Sides 6 8 10,Sides 6 8 10,Sides 8 15 17,Sides 9 12 15,Sides 5 12 13,Sides 9 12 15,Sides 12 16 20,Sides 8 15 17,Sides 15 20 25,Sides 12 16 20,Sides 15 20 25]

Вот мое решение:

removeElementFromList :: [SidesType] -> SidesType -> [SidesType]
removeElementFromList lst element  = 
                      let (Sides a b c) = element
                      in [(Sides x y z) | (Sides x y z) <- lst, (x /= a) || (y /= b)]

removeDuplicateFromList :: [SidesType] -> [SidesType] -> [SidesType]
removeDuplicateFromList inlist outlist 
                        | (length outlist) == 0 = inlist
                        | otherwise = 
                          let element = head outlist
                              b = tail outlist
                              filtered = removeElementFromList b element
                      in removeDuplicateFromList (inlist ++ [element]) filtered

Мне просто интересно, есть ли какой-нибудь другой способ написать этот код более понятным способом?

Answer 1

Как обычно, есть функция «By», которая добавляет гибкость:

nubBy :: (a -> a -> Bool) -> [a] -> [a]

PS Хотя это O (n ^ 2)

Answer 2

Вы уже получаете Show для своего типа данных.Если вы также получили Eq, вы можете использовать nub из module Data.List.

Answer 3

Сначала выведите также класс заказа:

data XYZ = XYZ .... deriving (Show, Eq, Ord)

Или напишите свой экземпляр на уравнении:

instance Eq XYZ where
a == b = ...

Тогда будьте умны и используйте Дерево![Деревья информатики растут сверху вниз!] [1]

import qualified Data.Map.Strict as Map

removeDuplicates ::[a] -> [a]
removeDuplicates list = map fst $ Map.toList $ Map.fromList $ map (\a -> (a,a)) list

Сложность (справа налево) для списка длиной N:

1. карта списка:O (N)
2. Map.fromList: O (N * log N)
3. Map.toList: O (log N)
4. отобразить список с длиной списка меньше илиравно N: O (N)

Они вызываются последовательно, это означает, что между сложностями деталей есть плюсы => O (2 * N + N * log N + log N)= O (N * log N)

Это намного лучше, чем обход N ^ 2 раза по списку!См .: Вольфрам Альфа-сюжеты .Я включил 2 * N также по причинам сравнения.

2 + 3: http://hackage.haskell.org/package/containers-0.5.4.0/docs/Data-Map-Strict.html

[1]: поиск по википедии для дерева информатики

Answer 4

Использовать Data.List.nub