Haskell에 'uniqueBy'처럼 작동하는 함수가 있습니까?

Nov 21 2020

나는 호출 할 수있는 기능이 필요 uniqueBy것이다 제거 모두 같은이 튜플의리스트의 요소 snd로도 그 중 하나를 유지하지 않고 값을 nubBy겠습니까합니다. 예를 들면

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

반환해야 []하지만

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

반환 [(1,2)]합니다.

슬프게도이 기능 uniqueBy은 존재하지 않으며, 쉬운 방법이 있어야한다고 확신하지만 대체 기능이나 구현 방법을 찾을 수없는 것 같습니다.

답변

2 WillemVanOnsem Nov 21 2020 at 23:12

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)]

nubBy처럼 얻어 nub, O (N 2 ) 시간. 따라서 요소를 정렬 할 수있는 경우 먼저 정렬 한 다음 다음 과 같은 고유성 필터 수행하는 것이 더 효율적입니다 .

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)의 중복을 필터링합니다 .