[Haskell-cafe] Matrices in Haskell

[Matthew Brecknell]

Ivan Miljenovic:
> As such, I'd like to know if there's any way of storing a an n-by-n
> matrix such that the algorithm/function to get either the rows or the
> columns is less than O(n^2) like transposition is.  I did try using an
> Array, but my (admittedly hurried and naive) usage of them took longer
> than a list of lists, was more difficult to manipulate, and wasn't
> required separate inverse functions to row and cols.  Also, since I
> need to look all throughout the list of values, it's still O(n^2), but
> this time for both rows and columns.

I'm not sure I see the problem, since any operation that touches all the
elements of a n-by-n matrix will be at least O(n^2). For such an
operation, a transposition should just add a constant factor.

When you tried using Arrays, I presume you used an array indexed by a
pair (i,j), and just reversed the order of the index pair to switch from
row-wise to column-wise access? It's hard to see how that would slow you
down. Perhaps the slowdown was caused by excessive array copying?
Immutable arrays can be efficient for algorithms that write a whole
array at once, but usually not for algorithms that modify one element at
a time.

I think you'll need to show specific functions that are performing below
expectation before the list will be able to help.

For problems like latin squares and sudoku, also try thinking "outside
the matrix". Do you really need to structure the problem in terms of
rows and columns? What about a set of mutually-intersecting sets of
cells?