[Haskell-cafe] 2D Array

Cale Gibbard cgibbard at gmail.com
Sun Dec 3 22:23:04 EST 2006

You might want to consider using a DiffArray, though if the
backtracking is of just the wrong sort, you might get worse
performance than you want. Updates are O(length xs) where xs is the
list of updates to be performed (so O(1) in the singleton case), but
lookups into older versions of the array get slower by a constant
amount every time an update is performed. (The semantics are
referentially transparent, the performance is not.) However, updating
an old version will cause a fresh copy to be made, and lookups will be
fast again after that.

On 03/12/06, Tony Morris <tmorris at tmorris.net> wrote:
> I wish to pass a 2 dimensional array to use in a back-tracking
> algorithm. Since I will be doing lots of inserts, a Data.Array is
> unsuitable. It seems that a Map Int (Map Int a) is the most suitable
> structure, but this seems cumbersome.
> Is there anything more appropriate?
> --
> Tony Morris
> http://tmorris.net/
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe

More information about the Haskell-Cafe mailing list