Haskell中是否有一个函数可以像"uniqueBy"一样工作? [英] Is there a function in Haskell that would work like 'uniqueBy'?

问题描述

我需要一个可以称为 uniqueBy 的函数，该函数可以删除元组列表中的 all 元素具有相同 snd 值的代码，即使其中的一个都不像 nubBy 那样保留.例如，

I need a function that could be called uniqueBy that would remove all elements in a list of tuples that have the same snd value, without keeping even one of them as nubBy would. For example,

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

应返回 [] ，而

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

将返回 [(1,2)] .

可悲的是，此功能 uniqueBy 不存在，尽管我确定有替代功能或一种自己实现的方法，但我似乎找不到是一种简单的方法.

Sadly this function uniqueBy does not exist and I can't seem to find an alternative function or a way to implement it myself, although I'm sure there has to be an easy way.

推荐答案

Data.List 模块具有

The Data.List module has a nubBy :: (a -> a -> Bool) -> [a] -> [a] function. You thus can use this like:

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 ² )时间.因此，如果您可以对元素进行排序，则对一阶元素进行排序并 then 执行uniqness过滤器会更有效，例如:

nubBy takes, just like nub, O(n²) time. So in case you can order the elements, it is more efficient to first order and then perform a uniqness filter, like:

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)

这样做的一个缺点是它不能与无限列表一起使用，而且该顺序将不被保留，但是在这里w会因此过滤掉 O(n log n).

A disadvantage of this is that it can not work with infinite lists, and furthermore that the order will not be preserved, but here w thus filter out duplicates in O(n log n).

这篇关于Haskell中是否有一个函数可以像"uniqueBy"一样工作?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！