[Haskell-cafe] Matrices in Haskell
Ivan Miljenovic
ivan.miljenovic at gmail.com
Mon Mar 19 18:39:21 EDT 2007
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
More information about the Haskell-Cafe
mailing list