haskell - 是否有类似于 Haskell 中列表的数据结构，它允许替换 O(1) 中的元素？

Question

到目前为止，我只找到了向量和序列，但它们都不能替换 O(1) 中的列表元素。这样的数据结构当然会违反 Haskells 结构的不可变特性，但也许仍然存在一些肮脏的实现？欢迎每个反馈。

标签： haskelldata-structures

Answer 1

正如您自己建议的那样 - 我也很确定O (1) 中的安全、纯功能更新是不可能的。可能在O (log n ) 中具有树状实现；例如，[a]您可以使用Data.Map.Map Int a连续的索引区域来代替。此外，可以对列表或向量中的k ≤ n 个元素进行批量更新，只需O ( n ) 而不是手动逐个插入它们所需的O ( k·n )。退房。//

如果这些对你来说都不够快，那么是的，你将需要进入可变性的黑暗领域。幸运的是，Haskell 为这样的旅程提供了一个很好的安全盔甲和手电筒：STmonad。它的工作方式是，将需要进行可变更新的整个区域包装在runST. 在该区域内，您使用MVectors，它支持O (1)可变元素更新，就像在命令式语言中一样。但是多亏了类型系统技巧，runST确保所有这些副作用都限制在本地范围内。