haskell - 如何在 Haskell 的数据结构中获得恒定时间访问(如在数组中)？

Question

我会直截了本地说 - 有没有办法在 Haskell 中拥有一个动态大小的恒定时间访问数据结构，就像任何其他命令式语言中的数组一样？

我确信某处有一个模块可以为我们神奇地做到这一点，但我希望能对人们如何以一种功能性的方式做到这一点有一个一般性的解释:)

据我所知，Map使用二叉树表示，所以它有 O(log(n)) 访问时间，列表当然有 O(n) 访问时间。

此外，如果我们让它不可变，它就会是纯的，对吧？

有什么想法可以解决这个问题(除了模板 Haskell 等中的 Array = Array { one :: Int, two :: Int, three :: Int ...} 之类的东西)？

Answer 1

如果您的 key 与 Int 同构那么你可以使用IntMap因为它的大部分业务是O(min(n,W)) , 其中 n是元素的数量，W是 Int 中的位数(通常为 32 或 64)，这意味着随着集合变大，每个单独操作的成本会收敛到一个常数。