gcb*_*son 5 haskell data-structures
作为一个练习我写了一个实现了的最长递增子算法,最初在Python,但我想这个翻译成哈斯克尔.简而言之,算法涉及对整数列表进行折叠,其中每次迭代的结果是整数数组,这是整数元素更改或将一个元素附加到前一个结果的结果.
当然,在Python中,您只需更改数组的一个元素即可.在Haskell中,您可以在每次迭代时替换一个元素时重建数组 - 但这似乎很浪费(在每次迭代时复制大部分数组).
总之就是我正在寻找的是一个高效的Haskell数据结构,是"N"对象的有序集合和支持的操作:lookup i,replace i foo,和append foo(其中i为[0到n-1]).建议？
Seq也许是来自 的标准类型Data.Sequence。虽然不完全是 O(1)，但也相当不错了：
index(你的lookup) 和adjust(你的replace) 是 O(log(min(索引, 长度 - 索引)))
(><)（你的append）是 O(log(min( length1 , length2 )))
它基于树结构（特别是 2-3 指树），因此它应该具有良好的共享属性（这意味着它不会复制整个序列以进行增量修改，并且执行速度也会更快）。请注意，Seq与列表不同，s 是严格的。