[Haskell-cafe] Matrices in Haskell

[Vincent Kraeutler]

Matthew Brecknell wrote:
> 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?
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
>
>   
i think you might also want to check up on

http://en.wikibooks.org/wiki/Haskell/Hierarchical_libraries/Arrays

if you intend to do a significant number of incremental updates, it is my
(not particularly well-informed) understanding that you should use either
mutable arrays (Data.Array.ST  together with runST), or Data.Array.Diff
with explicit sequencing.

both approaches are discussed in the above wikipedia entry.

cheers,
v.

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 249 bytes
Desc: OpenPGP digital signature
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20070320/b674195b/signature.bin