模式匹配数组

Question

我有一个返回数组最小值的函数.

该函数有类型:

min : int array -> int

它的实施是:

let rec min a = match a with
  | [] -> 1000000000
  | x :: [] -> x
  | x :: xs -> let ms = min xs in if x < ms then x else ms;;

但是,我收到此错误:

Found min with unexpected type: 
Wrong type int list -> int.

那么我如何模式匹配数组呢？

Answer 1

您在模式中使用列表表示法,这会导致问题.数组常量如下所示:[| 3; 4; 5 |]

如您所料,数组模式看起来相同:

let f = function
| [| |] -> "empty"
| [| _ |] -> "one"
| [| _; _ |] -> "two"
| _ -> "many"

每个数组模式都匹配特定大小的数组.至少具有一定大小的数组是不匹配的.这与可获得这种灵活性的列表形成对比.

而不是使用模式匹配,处理数组的更有用的方法可能是使用Array.fold_left或Array.fold_right.

可能你已经习惯了一种语言,其中数组和列表或多或少是相同的.在OCaml中,您必须选择要使用的那个.

Answer 2

与列表不同，数组不是归纳定义的。例如，列表可以是空列表，也可以是一个元素和另一个列表的对。归纳数据定义很好，因为它们允许归纳地（即递归地）推理数据。数组是一种非常不同的数据结构，它被定义为固定数量的相同类型的元素。因此，您的算法不适用于数组。问题不仅仅在于语法。您无法通过数组归纳来表达最小值。您需要找到其他方法来表达最小值，例如，A大小数组的最小值N是这样的元素，m，对于i, 0 <= i < N我们所有的元素m <= A(i)。如果你遵循这个定义，那么你可以直接实现它。从第一个元素开始作为最小值的近似值，然后继续处理下一个元素，如果它小于当前的最小值，则更新您的近似值。检查完所有元素后，您的最小值将满足所需的属性。

关于空情况，那么您可以决定空数组的最小值未定义。Tha 将使您的函数成为非全部函数，您可以通过设置返回类型来显式表示，int option或者通过引发异常并在注释中声明该函数仅为非空数组定义来隐式表示。或者，您可以返回max_int作为空数组的最小元素，因为空集的最大下界是宇宙的最大值（max_int在我们的例子中）。