1

我有数据类型：

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

我只是想知道是否还有其他方法可以用更多的haskell方式编写这段代码？

4

4 回答 4

7

像往常一样，有“By”功能，增加了灵活性：

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

PS虽然是O(n^2)

于 2010-12-03T08:40:04.693 回答
3

您已经Show为您的数据类型派生了。如果您还派生Eq，则可以使用nubfrom module Data.List。

于 2010-12-03T11:06:26.567 回答
0

使用 Data.List.nub

于 2010-12-03T08:11:31.307 回答
0

首先也派生订单类：

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

或者写你的 Eq 实例：

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 次要好得多！请参阅：wolframAlpha 图。出于比较的原因，我也包括了 2*N。

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

[1]：在维基百科中搜索计算机科学树

于 2014-03-11T23:28:34.943 回答