Growing arrays in Haskell

Question

I have the following (imperative) algorithm that I want to implement in Haskell:

Given a sequence of pairs [(e0,s0), (e1,s1), (e2,s2),...,(en,sn)], where both "e" and "s" parts are natural numbers not necessarily different, at each time step one element of this sequence is randomly selected, let's say (ei,si), and based in the values of (ei,si), a new element is built and added to the sequence.

How can I implement this efficiently in Haskell? The need for random access would make it bad for lists, while the need for appending one element at a time would make it bad for arrays, as far as I know.

Thanks in advance.

Answer 1

I suggest using either Data.Set or Data.Sequence, depending on what you're needing it for. The latter in particular provides you with logarithmic index lookup (as opposed to linear for lists) and O(1) appending on either end.

Answer 2

"while the need for appending one element at a time would make it bad for arrays" Algorithmically, it seems like you want a dynamic array (aka vector, array list, etc.), which has amortized O(1) time to append an element. I don't know of a Haskell implementation of it off-hand, and it is not a very "functional" data structure, but it is definitely possible to implement it in Haskell in some kind of state monad.

Answer 3

If you know approx how much total elements you will need then you can create an array of such size which is "sparse" at first and then as need you can put elements in it. Something like below can be used to represent this new array:

data MyArray = MyArray (Array Int Int) Int

(where the last Int represent how many elements are used in the array)

Answer 4

If you really need stop-and-start resizing, you could think about using the simple-rope package along with a StringLike instance for something like Vector. In particular, this might accommodate scenarios where you start out with a large array and are interested in relatively small additions.

That said, adding individual elements into the chunks of the rope may still induce a lot of copying. You will need to try out your specific case, but you should be prepared to use a mutable vector as you may not need pure intermediate results.

If you can build your array in one shot and just need the indexing behavior you describe, something like the following may suffice,

import Data.Array.IArray

test :: Array Int (Int,Int)
test = accumArray (flip const) (0,0) (0,20) [(i, f i) | i <- [0..19]]
  where f 0 = (1,0)
        f i = let (e,s) = test ! (i `div` 2) in (e*2,s+1)