performance - Haskell 函数 nub 效率低下

Question

我对 Haskell 标准库 Data.List 中“nub”(选择唯一值)函数的实现感到困惑。 GHC 的实现是

nub l                   = nub' l []
  where
    nub' [] _           = []
    nub' (x:xs) ls
        | x `elem` ls   = nub' xs ls
        | otherwise     = x : nub' xs (x:ls)

据我所知，这在最坏情况下的时间复杂度为 O(n^2)，因为对于一个唯一值列表，它必须将它们全部比较一次才能确定它们实际上是唯一的。

如果使用哈希表，构建表的复杂度可以降低为 O(n) + O(1)，用于检查哈希表中每个值与先前值的对比。当然，这不会生成有序列表，但如果有必要，也可以使用 GHC 自己的有序 Data.Map 在 O(n log n) 中生成。

为什么要为一个重要的库函数选择如此低效的实现？我知道效率不是 Haskell 的主要关注点，但至少标准库可以努力为工作选择(渐近)最佳数据结构。

Answer 1

在 Haskell 中，效率是一个相当重要的问题，毕竟该语言的性能与 Java 相当，并且在内存消耗方面优于它，但当然它不是 C。

您的问题的答案非常简单:Prelude 的nub 只需要一个Eq 约束，而任何基于Map 或Set 还需要 Ord 或 Hashable。