Looking for an efficient array-like structure that supports "replace-one-member" and "append"

Question

As an exercise I wrote an implementation of the longest increasing subsequence algorithm, initially in Python but I would like to translate this to Haskell. In a nutshell, the algorithm involves a fold over a list of integers, where the result of each iteration is an array of integers that is the result of either changing one element of or appending one element to the previous result.

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

In summary what I'm looking for is an efficient Haskell data structure that is an ordered collection of 'n' objects and supports the operations: lookup i, replace i foo, and append foo (where i is in [0..n-1]). Suggestions?

Answer 1

Perhaps the standard Seq type from Data.Sequence. It's not quite O(1), but it's pretty good:

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

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

It's based on a tree structure (specifically, a 2-3 finger tree), so it should have good sharing properties (meaning that it won't copy the entire sequence for incremental modifications, and will perform them faster too). Note that Seqs are strict, unlike lists.

Answer 2

I would try to just use mutable arrays in this case, preferably in the ST monad.

The main advantages would be making the translation more straightforward and making things simple and efficient.

The disadvantage, of course, is losing on purity and composability. However I think this should not be such a big deal since I don't think there are many cases where you would like to keep intermediate algorithm states around.