我一直在考虑Haskell - 所以仍然是一个初学者.
我一直在考虑计算列表中项目的频率.在具有可变数据结构的语言中,这通常使用哈希表来解决 - 例如Python中的dict或Java中的HashMap.这种解决方案的复杂性是O(n) - 假设哈希表完全适合内存.
在Haskell中,似乎有两种(主流)选择 - 对数据进行排序然后对其进行分组和计数或使用Data.Map.如果使用排序,它将主导解决方案的运行时,因此复杂度为O(n log n).同样,Data.Map使用平衡树,因此在其中插入n个元素也将具有复杂度O(n log n).
如果我的分析是正确的,那么我认为通过诉诸可变数据结构可以最有效地解决这个特定问题.还有其他类型的问题吗？一般来说,使用Haskell的人会如何处理这样的事情？
目前尚不清楚我们是否可以用纯语言实现任何具有最佳复杂性的算法。Nicholas Pippenger 已经证明，与最优算法相比，在纯严格语言中存在一个必然具有 log(n) 惩罚的问题。然而，有一篇后续论文表明这个问题在惰性语言中有一个最优解决方案。所以最终我们真的不知道。尽管大多数人似乎认为某些问题存在固有的 log(n) 惩罚，即使对于惰性语言也是如此。