Re: [Haskell-cafe] Re: Matrices in Haskell

22 Mar 2007

      Sorry for the double post before... must have hit "send" without
noticing :s (it would also help if I posted this to the mailing list
instead of just to myself!).

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).

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.

Thoughts/comments on this data structure?

On Wed, 2007-03-21 at 08:26 +1000, Ivan Miljenovic wrote:
...
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

email: Ivan.Miljenovic@gmail.com

 ______________________________________ 
/ The linuX Files -- The Source is Out \
\ There.                               /
 -------------------------------------- 
   \
    \
        .--.
       |o_o |
       |:_/ |
      //   \ \
     (|     | )
    /'\_   _/`\
    \___)=(___/