Haskellに「uniqueBy」のように機能する関数はありますか？

Question

私が呼び出される可能性機能必要uniqueByでしょう削除すべて同じ持つタプルのリストの要素sndとしても、それらの一方を維持せずに値を、nubBy考えを。例えば、

uniqueBy [(1,1),(2,1)]

を返す必要が[]ありますが、

uniqueBy [(1,1),(1,1),(1,2)]

を返し[(1,2)]ます。

残念ながら、この関数uniqueByは存在せず、別の関数やそれを自分で実装する方法を見つけることができないようですが、簡単な方法が必要だと確信しています。

Answer 1

Data.Listモジュールは、持っているnubBy :: (a -> a -> Bool) -> [a] -> [a]機能を。したがって、次のように使用できます。

import Data.Function(on)
import Data.List(nubBy)

uniqueOnSnd :: Eq b => [(a, b)] -> [(a, b)]
uniqueOnSnd = nubBy ((==) `on` snd)

例えば：

Main> uniqueOnSnd  [(4,1), (5,2), (3,1), (2,0)]
[(4,1),(5,2),(2,0)]

nubByO（n ²）時間と同じようnubにかかります。だから、場合にあなたはそれが最初の順番に、より効率的である、要素を注文することができますし、その後のように、uniqnessフィルタを実行します。

import Data.Function(on)
import Data.List(sortBy)

nubOrderBy :: (a -> a -> Ordering) -> [a] -> [a]
nubOrderBy cmp = go . sortBy cmp
    where go (x1:xs) = x1 : go (dropWhile ((EQ ==) . cmp x1) xs)
          go [] = []

uniqueOnSnd :: Ord b => [(a, b)] -> [(a, b)]
uniqueOrdOnSnd = nubOrderBy (compare `on` snd)

これの欠点は、無限のリストでは機能せず、さらに順序が保持されないことですが、ここでは、O（n log n）の重複を除外します。