haskell - 某些问题的最有效解决方案是否需要可变数据？

Question

我一直在涉足 Haskell - 所以仍然是一个初学者。

我一直在考虑计算列表中项目的频率。在具有可变数据结构的语言中，这通常使用哈希表来解决 - 例如 Python 中的 dict 或 Java 中的 HashMap。这种解决方案的复杂性是 O(n) - 假设哈希表可以完全适合内存。

在 Haskell 中，似乎有两种(主流)选择——对数据进行排序，然后对其进行分组和计数，或者使用 Data.Map。如果使用排序，它会支配解决方案的运行时间，因此复杂度为 O(n log n)。同样，Data.Map 使用平衡树，因此向其中插入 n 个元素也将具有 O(n log n) 复杂度。

如果我的分析是正确的，那么我假设这个特定问题可以通过使用可变数据结构来最有效地解决。是否还有其他类型的问题也是如此？一般来说，使用 Haskell 的人如何处理这样的事情？

Answer 1

我们是否可以用纯语言实现具有最佳复杂度的任何算法的问题目前尚不清楚。 Nicholas Pippenger has proven与最优算法相比，在纯严格语言中存在一个问题必须有 log(n) 惩罚。但是，有一个 followup paper这表明该问题在惰性语言中具有最优解。所以说到底我们真的不知道。尽管似乎大多数人认为某些问题存在固有的 log(n) 惩罚，即使对于惰性语言也是如此。