matrix - 函数式编程中的有效矩阵

Question

我是 C/C++ 程序员，我开始学习 Racket/阅读 SICP。我有一个关于函数式编程中矩阵的有效表示的问题。

1. 函数式编程中矩阵最有效的表示形式是什么？老好的数组数组？我这么问是因为 SICP 作者使用矩阵列表。
2. 这是一个现实世界的问题:在我们的生产代码中，我们有一个函数在每个步骤中为矩阵单元设置随机值。简化的代码如下所示:

// 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);
}

这段代码简单有效。如何针对大型不可变矩阵以函数式风格编写有效的代码？是否可以？如果是，那么如何？

非常感谢您的回答!

Answer 1

正如奥斯卡所说，最传统的函数式编程方法是使用链表。然而，更直接(尽管有一些突变)的方法是使用向量。

但是，既然您提到您在 Racket 中执行此操作，您实际上可以使用 for/vector来制作你的矩阵。您可以使用向量的向量，如下所示:

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

生成一个 3x3 随机数向量。现在您可以使用vector-ref两次以从中获取元素。

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

您可以采用的另一种方法是采用类似 C 的方法，并对整个矩阵使用单个向量。当然，这需要您存储一个额外的宽度参数，但可以使事情变得更清晰。¹例如，您可以创建一个包含数字 1 到 9 的 3x3 矩阵:

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

现在您只需要一个 vector-ref 即可获取元素:

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

当然，如果您想经常这样做，那么将其包装到单个数据结构中是有意义的:

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

当然，您可以走得更远，只需多做一点工作和一个小宏，您甚至可以添加 for/matrix 和 in-matrix 作为循环构造以及矩阵数学库。但在某些时候，您将有效地创建 math/matrix附带打字 Racket 的库。²

_{¹当然这纯粹是主观的，也取决于您的程序。}

_{²从技术上讲，它也适用于标准的、无类型的 Racket，但速度要慢得多。}