haskell - 寻找支持 "replace-one-member"和 "append"的高效类数组结构

Question

作为练习，我写了an implementation longest increasing subsequence algorithm的，最初是用 Python 编写的，但我想将其转换为 Haskell。简而言之，该算法涉及对整数列表的折叠，其中每次迭代的结果是一个整数数组，该数组是更改其中一个元素或追加一个元素的结果到之前的结果。

当然，在Python中你可以只改变数组的一个元素。在 Haskell 中，您可以重建数组，同时在每次迭代时替换一个元素 - 但这似乎很浪费(在每次迭代时复制数组的大部分内容)。

总之，我正在寻找的是一种高效的 Haskell 数据结构，它是“n”个对象的有序集合，并支持以下操作:查找 i、替换 i foo 和 append foo (其中 i 位于 [0..n-1] 中)。有建议吗？

Answer 1

也许是标准Seq输入 Data.Sequence 。虽然不完全是 O(1)，但也相当不错了:

• index (您的lookup)和 adjust (您的 replace )是 O(log(min(index, length - index)))

• (><) (您的 append )是 O(log(min(length1, length2)))

它基于树结构(特别是 2-3 指树)，因此它应该具有良好的共享属性(这意味着它不会复制整个序列以进行增量修改，并且执行速度也会更快)。请注意Seq与列表不同，s 是严格的。