OCaml 新手：我将如何实施高斯消元法？

Question

我是 OCaml 的新手，我想实现高斯消元法作为练习。我可以使用有状态算法轻松完成此操作，这意味着将矩阵保留在内存中并通过传递对它的引用来递归操作它。

然而，这种有状态性有点像命令式编程。我知道 OCaml 中有能力做到这一点，但我想问是否有一些我没有首先想到的聪明的功能方法。

Answer 1

OCaml 数组是可变的，很难避免像命令式语言中的数组一样对待它们。

Haskell 有不可变数组，但根据我对 Haskell 的（有限）经验，在大多数情况下你最终会切换到一元的、可变的数组。对于某些特定目的来说，不可变数组可能是令人惊奇的。我一直想象你可以在 Haskell 中编写一个漂亮的动态编程实现，其中数组条目之间的依赖关系完全由其中的表达式定义。关键是您实际上只需要指定每个数组条目的内容一次。我不认为高斯消除遵循这种模式，因此它似乎不太适合不可变数组。不过，看看它的效果如何会很有趣。

Answer 2

您可以使用Map来模拟矩阵。键是一对引用行和列的整数。您需要使用自己的 get x y 函数来确保 x x y 。 n 和 y n 但不是直接访问 Map。 （编辑）您可以直接使用Pervasives中的比较功能。

module OrderedPairs = struct
    type t = int * int
    let compare = Pervasives.compare
end                     
module Pairs = Map.Make (OrderedPairs)

let get_ n set x y =
    assert( x < n && y < n ); 
    Pairs.find (x,y) set

let set_ n set x y v = 
    assert( x < n && y < n ); 
    Pairs.add (x,y) set v

实际上，拥有一组通用函数（至少 get x y 和 set x y），而不指定实现，将是一个更好的选择。然后，这些函数可以传递给函数，或者通过函子在模块中实现（这是一个更好的解决方案，但拥有一组函数来完成您需要的操作将是第一步，因为您是 OCaml 新手）。这样你就可以使用Map、Array、Hashtbl或者一组函数来访问硬盘上的文件来实现矩阵，如果你想要的话。这是函数式编程真正重要的方面；您相信接口而不是利用副作用，而不用担心底层实现——因为它被认为是纯粹的。

Answer 3

到目前为止的答案是使用/模拟可变数据类型，但是函数式方法是什么样的？

为了看清楚，让我们将问题分解为一些功能组件：

高斯消除涉及一系列行运算，因此首先定义一个采用 2 行和缩放因子的函数，并返回行运算的结果是有用的。

我们想要的行操作应该从特定行中消除变量（列），因此让我们定义一个函数，该函数接受一对行和一个列索引，并使用先前定义的行操作返回修改后的行，其中该列条目为零。

然后我们定义两个函数，一个将矩阵转换为三角形式，另一个通过依次消除每一列将三角矩阵反向替换为对角形式（使用之前定义的函数）。我们可以迭代或递归列，并且矩阵可以定义为列表、向量或列表、向量或数组的数组。输入没有改变，但是返回了一个修改后的矩阵，所以我们最终可以这样做：

let out_matrix = to_diagonal(to_triangle in_matrix);

它的功能不在于数据类型（数组或列表）是否可变，而在于它们的使用方式。这种方法可能不是特别“聪明”，也不是在 OCaml 中进行高斯消除的最有效方法，但使用纯函数可以让您清晰地表达算法。