Haskell 函数 nub 效率低下

我对 Haskell 标准库中“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。

你的问题的答案很简单：前奏曲nub只需要一个Eq约束，而任何基于的实现Map or Set还需要一个Ord or Hashable.