Finding an effective array structure that supports the replace-one-member and append functions,

Question

As an exercise, I wrote an implementation of a growing subsequence algorithm , first in Python, but I would like to translate this into Haskell. In a nutshell, the algorithm includes a convolution over the list of integers, where the result of each iteration is an array of integers, which is the result of either changing one element or adding one element to the previous result.

Of course, in Python you can just change one element of the array. In Haskell, you can rebuild the array by replacing one element in each iteration, but it seems wasteful (copying most of the array in each iteration).

In general, I seek Haskell efficient data structure that is an ordered collection of "n" of facilities and supports operations: lookup i, replace i fooand append foo(where iin [0..n-1]). Suggestions?

Answer 1

Perhaps the standard Seqtype Data.Sequence. This is not exactly O (1), but it is pretty good:

• index(your lookup) and adjust(your replace) - O (log (min (index, length - index)))

• (><)(your append) is O (log (min (length1, length2)))

( , ), ( , ). , Seq , .

Answer 2

, ST.

, .

, , . , , , , .