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-way で記述する他の方法があるかどうか疑問に思っています。

4

4 に答える 4

7

いつものように、柔軟性を追加する「By」機能があります。

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

PS O（n ^ 2）ですが

于 2010-12-03T08:40:04.693 に答える
3

あなたはすでにShowあなたのデータ型を導き出しています。も導出する場合は、からEq使用できます。nubmodule Data.List

于 2010-12-03T11:06:26.567 に答える
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]: ウィキペディアで Computer Science Tree を検索

于 2014-03-11T23:28:34.943 に答える
0

Data.List.nub を使用する

于 2010-12-03T08:11:31.307 に答える