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