[Haskell-cafe] Re: Matrices in Haskell

[Ivan Lazar Miljenovic]

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 <apfelmus at quantentunnel.de> 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 at gmail.com

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

-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: This is a digitally signed message part
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20070322/71a2553d/attachment.bin