函数式编程中的有效矩阵

Question

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

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

// 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

正如 Óscar 所说，最传统的函数式编程方法是使用链表。然而，更直接（尽管有一些变化）的方法是使用向量。

但是，既然你提到你在 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，但速度要慢得多。}

Answer 2

SICP 的作者想要教授计算机科学，特别是函数式编程。感兴趣的不是在 GNU/MIT-Scheme 解释器中展示不同的工具。 40 年来，我一直热爱 SICP 作为灵感来源。你应该使用向量！

函数式编程中的有效矩阵

Effective matrix in functional programming

matrix

scheme

racket

sicp