performance - Haskell函数小结效率低下

我对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的主要关注点，但是至少标准库可以努力选择(渐近地)最佳数据结构来完成工作。

最佳答案

在Haskell中，效率毕竟是一个令人关注的问题，毕竟该语言的性能与Java相当，并且在内存消耗方面超过了Java，但当然不是C。

您的问题的答案非常简单:Prelude的nub仅需要Eq约束，而任何基于Map或Set的实现也都需要Ord或Hashable。