Effective matrix in functional programming

I am C/C++ programmer and I started learning Racket / reading SICP. I have a question about effective representation of matrices in functional programming.

What is the most effective representation for matrices in functional programming? Old good array of arrays? I am asking because SICP authors use lists of lists for matrices.
Here is a real-world problem: in our production code we have function which sets random values to matrix cells on each step. The simplified code looks like this:

// up to N random cells initialized with random values

// matrix is a current state of the game field

for (n = 0; n < Random(N); n++)
{
    matrix[Random(X)][Random(Y)] = Random(MAX);
}

This code is simple and effective. How to write this code effective in functional style for a large immutable matrix? Is it possible? If yes, then how?

Thank you very much for your answer!

Solution

As Óscar said, the most traditional functional programming approach would be to use linked lists. However, a more direct (albeit with some mutation) approach would be to use vectors.

However, since you mentioned you were doing this in Racket, you can actually use for/vector to make your matrix. You can either either use a vector of vectors, as in:

(define my-matrix
  (for/vector ([i (in-range 3)])
    (for/vector ([j (in-range 3)])
      (random))))

which makes a 3x3 vector of random numbers. Now you can use vector-ref twice to get an element out of it.

;; Evaluates to the middle most cell in the matrix
(vector-ref (vector-ref my-matrix 1) 1)

Another approach you can do is to take a C-like approach, and use a single vector for the whole matrix. This requires you to store an extra argument for the width of course, but can make things a bit cleaner.¹ For example, you could make a 3x3 matrix that contains the numbers 1 through 9:

(define matrix-width 3)
(define matrix
  (for/vector ([i (in-range 1 10)])
    i))

And now you only need a single vector-ref to get your element:

;; This also gets the middle most cell.
(vector-ref matrix (+ 1 (* 1 matrix-width)) ; => 5

Of course, if you want to do this a lot, it make sense to wrap this into a single data-structure:

(struct matrix (width data))
(define (make-matrix width height)
  (make-vector (* width height)))
(define (matrix-ref m i j)
  (vector-ref (matrix-data m) (+ i (* j (matrix-width m)))))
(define (matrix-set! m i j v)
   (vector-set! (matrix-data m) (+ i (* j (matrix-width m))) v))

Of course, you could go even further, and with a little more work and a small macro and you can even add for/matrix and in-matrix as looping constructs, as well as matrix math library. But at some point you will have effectively made the math/matrix library which comes with typed racket.²

_{¹Of course this is purely subjective, and will also depend on your program.}

_{²Technically it also works with standard, untyped, Racket, but much slower.}