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?

• rampion: You could just use a mutable array. I've had good experiences with MVector.
• Sjoerd Visscher: MVector has O(n) append/cons/snoc.
• n. m. could be an AI: Why do you need append? The ultimate size is known from the start.
• gcbenison: @n.m. The maximum size is known at the start, but for most input it ends up being significantly smaller than this. Good point though, append is not strictly needed.
• gcbenison: @n.m. An extreme case - for the input [1000,999,..1] - the result array never grows beyond size 1.

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.

• Louis Wasserman: Seq is basically the best way to do this unless you're willing to work in IO or ST.

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.

• Yuval Langer: This page will tell you which type of array you should be using and in what cases: haskell.org/haskellwiki/Arrays Also, many thanks, @missingno