[Haskell-cafe] Re: Matrices in Haskell

[apfelmus]

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