types - 在 OCaml 中用数组、列表或映射定义一个 int 矩阵？

Question

我需要定义一个 int 矩阵作为类型。矩阵的一列或一行代表一个城市，矩阵中的一个元素代表行城市与列城市之间的距离。矩阵的维度可能会改变(我们可能会添加或删除城市)，但它总是很小。

我在int array array, int list list 和定义如下的map类型之间犹豫:

module MatOrd = struct 
  type t = string * string
  let compare ((a, b): string * string) ((c, d) : string * string) = 
    if Pervasives.compare a  c <> 0
    then Pervasives.compare a c 
    else Pervasives.compare b d
end

module MatMap = Map.Make(MatOrd)

然后 int MatMap.t 可以表示一个 int 矩阵。这个定义的一个好处是我可以直接把城市的名字写成矩阵的坐标。而对于int array array和int list list，看来我得死记硬背坐标的意义了……

此外，我们真的不能对数组进行模式匹配吗？例如，我们不能写:

match a_array with
  [| first_element; the_rest_elements |] -> ...

根据我提到的和没有提到的优点和缺点，您建议使用哪种类型？

Answer 1

这种或那种类型的适用性真的取决于您打算用它实现哪些操作。你会用你的类型计算什么？

例如，您可能想利用在某处实现的矩阵运算，例如 min-plus multiplication ，这可能会帮助您解决最短路径问题。在这种情况下，使用矩阵是有意义的，并且有一个单独的函数 string -> int 将城市名称转换为矩阵坐标。另一方面，如果您只想要一个计算稀缺的数据存储，Map 类型(如上面的类型)可能更有意义。

如果不知道你想计算什么，很难给出非常有见地的答案，但至于你的建议:

• 记住列表是不可变的，因此 int list list 的实用性有限

• 如果您制作二维数组，请注意数组是可变引用，并且会相应地处理影响，以便在以下内容之后:

  let a = Array.make 3 0;;
  let a = b;;
  b.(0) <- 42;;
  

  a.(0) 等于 42。

  该语言具有急切的求值策略，因此另一个警告是您不应按以下方式创建数组:

  let m = Array.make 2 (Array.make 3 0);;
  m : int array array = [|[|0; 0; 0|]; [|0; 0; 0|]|]
  m.(0).(0) <- 1;;
  - : unit = ()
  m;;
  - : int array array = [|[|1; 0; 0|]; [|1; 0; 0|]|]
  

  内部的 make 调用首先被求值，并且三个共享相同的引用你的外部数组的行。参见 the FAQ关于如何创建矩阵。

顺便说一句，您可以对数组进行模式匹配(relevant manual section 显示页面底部的模式)，但在放置模式变量时必须考虑数组的维度。值得庆幸的是，您可以使用 _，正如您所说，数组的维度非常小。