我感到困惑的结点的实施，在Haskell的标准库（选择唯一值）功能的 Data.List模块的。该GHC实施

I'm confused by the implementation of the 'nub' (select unique values) function in the Haskell standard library Data.List. The GHC implementation is

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

据我所知，这有邻最坏情况下的时间复杂度（N ^ 2），因为对于唯一值的列表，它以比较它们全部一次看到他们其实都是独一无二的。

As far as I can tell, this has a worst-case time complexity of O(n^2), since for a list of unique values it has to compare them all once to see that they are in fact unique.

如果中使用的一个哈希表，复杂性可以减少到O（n）的建设表+ O（1）在哈希表中核对previous值的每个值。当然，这不会产生一个有序的列表，但是，这也将有可能在为O（n log n）的使用GHC自己的命Data.Map中，如果这是必要的。

If one used a hash table, the complexity could be reduced to O(n) for building the table + O(1) for checking each value against previous values in the hash table. Granted, this would not produce an ordered list but that would also be possible in O(n log n) using GHC's own ordered Data.Map, if that is necessary.

为什么要选择这样一个低效率的实现的重要库函数？我理解的效率是不是一个主要关注在Haskell但至少在标准库可以作出努力，选择（渐近）最佳数据结构的工作。

Why choose such an inefficient implementation for an important library function? I understand efficiency is not a main concern in Haskell but at least the standard library could make an effort to choose the (asymptotically) best data structure for the job.

推荐答案

效率是Haskell中非常关注的问题，毕竟语言执行与Java相当，并击败它在内存消耗方面，但当然这不是C

Efficiency is quite a concern in Haskell, after all the language performs on par with Java, and beats it in terms of memory consumption, but of course it's not C.

在回答你的问题是pretty的简单：prelude的要点只需要一个式约束，而根据地图的任何实施或设置还要求要么是奥德或哈希。

The answer to your question is pretty simple: the Prelude's nub requires only an Eq constraint, while any implementation based on Map or Set would also require either an Ord or Hashable.