On Tue, 2007-03-20 at 15:09 +1000, Matthew Brecknell wrote:

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.

What I was hoping for was a data structure such that I could directly access the columns of the matrix, rather than having to apply a function to get to them. I didn't think it likely, but then again, a man can dream... ;)

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.

I've attached the code I had written using Arrays. Note that it wasn't the final version of my algorithms, etc. as I continued work a bit further using lists of lists, but the working behind them is just the same (just some extra optimizations, etc. are missing). Here's the way I was pulling out the rows and columns from the array: type Matrix a = IArray MatCoord a type MatCoord = (Int,Int) type Row a = Array Int a getRows :: Matrix a -> [Row a] getRows m = [newRow sr [(c,v) | ((r,c),v) <- vals, r == r'] | r' <- values sr] where sr = fst . snd . bounds $ m vals = assocs m unRows :: [Row a] -> Matrix a unRows = liftM2 newMatrix length addRowValues where addRowValue r = map (\ (c,v) -> ((r,c),v)) . assocs addRowValues = concat . zipWith addRowValue [1..] getCols :: Matrix a -> [Row a] getCols m = [newRow sc [(r,v) | ((r,c),v) <- vals, c == c'] | c' <- values sc] where sc = snd . snd . bounds $ m vals = assocs m unCols :: [Row a] -> Matrix a unCols = liftM2 newMatrix length addColValues where addColValue c = map (\ (r,v) -> ((r,c),v)) . assocs addColValues = concat . zipWith addColValue [1..] And here's an example where I used these functions. What it's doing is storing a list of all possible values for each cell in the matrix, then removing double ups. type Choices = [[Int]] prune :: Matrix Choices -> Matrix Choices prune = pruneBy cols . pruneBy rows where pruneBy (f,f') = f' . map reduce . f reduce :: Row Choices -> Row Choices reduce r = array size (map reducer vals) where size = bounds r vals = assocs r reducer (c,vs) = (c, vs `minus` singles) singles = getSingles r minus :: Choices -> Choices -> Choices xs `minus` ys = if single xs then xs else xs \\ ys

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?

I based my code upon the paper by Richard Bird and later implemented by Graham Hutton. I'm going to be re-writing it a bit, in terms of first generating the "shapes" that the Partial Latin Squares can take, then trying to fill in the numbers. I have considered using a graph-theory approach, but I have no idea where to even start to code it. Fundamentally, I'm trying to generate all Partial Latin Squares that fit a given criteria, so I need the rows/columns to ensure that I have no more than one instance of each value in each row or column. -- Ivan Lazar Miljenovic

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?

the difference can be in locality wrt the memory hierarchy: is the next element nearby most of the time (apart from array borders), or a row-/column-width away most of the time? i understand that, eg, fortran and c differ in their default interpretations of array layout, so naively translated benchmarks might suffer from running against the grain in one of the two (row-major loops over a column-major layout, or the other way round). claus

it seems unlikely to me that this would cause a degradation in performance with respect to lists...

that might depend on the number of operations per transposition, i guess. lists and explicit transpositions make it very obvious what is going on in terms of iteration order, so i would be tempted to group operations by whether they need a plain or transposed structure. arrays hide this kind of thing, so i might pay the cost for every transposed operation without the code warning me. the original poster was doing (transpose . op . transpose) for each out-of-order op in the list version, so that might be on par with what the array version does, or not. optimising array computations is a fun business. but i misread the part i quoted to talk about slowdown on switching between row-column and column-row, whereas it was generally about slowdown on switching variable-order operations from lists to arrays. so i assume that posters here were already aware of the transposition of layout affecting arrays as well. claus

On 21/03/07, apfelmus wrote:

Concerning Sudoku, there is a beautiful talk from R. Bird

http://icfp06.cs.uchicago.edu/bird-talk.pdf

I based my Latin Squares algorithms on Bird's Functional Pearl article "A Program to play Sudoku"

...

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.

You can use nested data types in order to ensure squareness, see also

C. Okasaki. From Fast Exponentiation to Square Matrices: An Adventure in Types http://www.eecs.usma.edu/webs/people/okasaki/pubs.html#icfp99

At first glance, this looks like the kind of thing I want. Thanks! -- Ivan Lazar Miljenovic

Ivan Lazar Miljenovic wrote:

Anyway, I had a thought today: what about using a quadruply linked list?

i.e.:

data QLNode a = Null | QLNode a (Right a) (Up a) (Left a) (Bottom a)

where Right, Up, Left and Bottom are just type synonyms of QLNode.

You could have only two nodes linked to (e.g. only the right and bottom ones), but I've put in four so that if I want to change an element in the middle of the matrix, I can do something like in the OOP world, with node.previous.next = newNode (not quite sure off the top of my head how to do this in Haskell).

As data structures are persistent (you cannot "change" values in place, you can only create new ones), you'll inevitably run into problems when updating elements. Assuming a rectangular shape and selector functions right, up, left, down :: QLNode a -> QLNode a for the four linked nodes, we have the following equalities (ignoring the fact that QLNode may be Null) right . left = left . right = id down . up = up . down = id right . down = down . right right . up = up . right ... right . up . left . right . down . down = right . down ... and so on. When updating an element, you'd have to make sure that each of those equalities still hold. It's possible but takes O(n) time per element update.

The advantage I see in this representation is that to access each individual row/column is O(n) for an n-by-n matrix. When I said in my initial post that I didn't want an O(n^2) function to get the columns, I meant that I didn't want to have to do an O(n^2) transpose function if I only wanted to access the kth column.

In case you do not update matrices but build them all at once (say via some kind of fmap), the quadruply linked list is indeed useful and gives O(n) read-access to all elements of a row. If you need single element/row/column writing as well, I guess you're better off with Okasaki's nested square matrices. Regards, apfelmus