[Haskell-cafe] Matrices in Haskell

[Ivan Miljenovic]

Some of you might recall me annoying people on #haskell over the New
Year about my Latin Squares project.  Well, I'm looking at re-doing it
from scratch, but the first thing I need to do is find a new way of
representing my square.

I have been using a list of lists ([[a]]) to represent a matrix.  The
problem with this data structure is that I need to be able to
manipulate matrices as both row-oriented and column-oriented data
structures, as I need to examine the values in the columns as well as
in the rows.  As it stands, I was doing this by transposing the
matrix, manipulating it, then transposing it back again.  This is a
pain, as it takes up about 15% to 20% of the run time.  The other
problem with using a list of lists is that the only reason I'm sure
that the matrix is valid (i.e. all the rows are the same length, etc.)
is because I created it that way, not because the data structure
requires it.

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 know that when doing something similar to this in Java a few years
ago (a primitive Sudoku solver, to be precise), I could represent the
rows and columns as to separate 2D arrays, with rows(i,j) pointing to
the same object as cols(j,i).  Is something like this possible in
Haskell?  in particular, I will be storing lists of possible values in
the cells of the matrix, so the capability to backtrack would be very
nice, as I'd be trying each value at a time to see if it is valid.

I'd also want to use such a matrix implementation next semester for a
project, which I plan on being a quick comparison of various
programming languages as to ease of use and efficiency for
matrix-based computing problems.

-- 
Ivan Lazar Miljenovic