Data.List中nubBy的实现不一致？

Question

我正在浏览nubByData.List中函数的源代码:

nubBy                   :: (a -> a -> Bool) -> [a] -> [a]
#ifdef USE_REPORT_PRELUDE
nubBy eq []             =  []
nubBy eq (x:xs)         =  x : nubBy eq (filter (\ y -> not (eq x y)) xs)
#else
nubBy eq l              = nubBy' l []
  where
    nubBy' [] _         = []
    nubBy' (y:ys) xs
       | elem_by eq y xs = nubBy' ys xs
       | otherwise       = y : nubBy' ys (y:xs)

现在在我看来,上面的两个版本彼此不同.如果我拿这个USE_REPORT_PRELUDE版本,我就知道了

nubBy (>) [1..10]
[1,2,3,4,5,6,7,8,9,10]

而其他实施产生

nubBy (>) [1..10]
[1]

这背后的原因是什么？

Answer 1

我认为这nubBy需要二进制布尔运算是等价关系.

这大致与sortBy需要预订关系(反身和传递)的精神相同.如果此要求无效,则quicksort和mergesort将成为非等效算法.Haskell报告的目的是允许实现使用它们中的任何一个(或另一个正确的排序算法).

类似地,如果nubBy允许比较是非等价的,则实施被不必要地限制为精确地使用参考Prelude算法,从而阻止使用更有效的替代方案.

说实话,传递给"...... By"的操作员的确切要求并不总是显而易见的.例如,sortBy的文档似乎只保证对总排序的正确性,虽然我期望实际的实现也适用于更大的排序类,只要结果被解释为由排序引起的等价.

nubBy的文档只是声明第一个参数是"用户提供的等式谓词".因此,它只能保证平等,而不是任意等价.

但是,我的感觉是,如果它的实现对于平等起作用,那么它也必须用于等价(当然,只要读取结果).这可能通过利用与该类型相关联的" 自由定理 " 来证明nubBy.我缺乏参数化专业知识背叛了我:)