查找 int 列表的不同元素

Question

我对 OCaml 还是个新手，想写一个函数来查找字母表，或者一个 int 列表的不同个体数字，return 它们作为一个列表。我想到了以下内容：

let rec find_alpha (list: int list) (acc: int list) =
   match list with
   |[]       -> acc
   |hd       -> if List.mem hd acc then acc else hd::acc
   |hd::tl   -> if List.mem hd acc then find_alpha tl acc else find_alpha tl hd::acc

编译器说：

|hd       -> if List.mem hd acc then acc else hd::acc
                            ^^^
Error: This expression has type int list but an expression was expected of type int list list
Type int is not compatible with type int list.

尽管消息非常明确，但我无法弄清楚为什么需要一个类型为 int list list 的表达式。我检查 hd 元素是否已经在 acc 列表中。如果是，我 return acc 作为我的结果，如果它不在 acc 中，我附加它并 return 它。

为什么要 int list list？

忘了说了，第一种情况[]应该是不可达的，不知道什么原因还是收进去了。我应该把它剪掉不是吗？

Answer 1

| hd -> if List.mem hd acc then acc else hd::acc

这种情况意味着 "match the whole list and name it hd in the following" 与

相比

| [hd] -> if List.mem hd acc then acc else hd::acc

意思是“匹配一个只有一个元素的列表并命名为hd.

特别是

| hd -> if List.mem hd acc then acc else hd::acc

List.mem hd acc 正在检查 int hd 列表是否属于列表 acc。这只有在 acc 是 int 列表的列表时才有意义。但是，您明确指出 acc 是一个 int 列表；产生您看到的编译器错误。

Answer 2

在模式匹配的第二行中，您使用 hd 作为模式。此模式匹配任何值并将其称为 hd。这使得 hd 在行

中成为 int list

|hd       -> if List.mem hd acc then acc else hd::acc

当编译器对 List.mem 的调用进行类型检查时，它恰好首先分析了第一个参数。由于此时编译器已经知道 hd 具有类型 int list，因此它推断第二个参数必须具有类型 int list list，因为 List.mem 的类型（这是 'a -> 'a list -> bool，'a 在此处实例化为 int list）。如果函数 List.hd 以相反的顺序接受它的参数，或者编译器以相反的顺序对函数调用进行类型检查，则投诉将是 hd 具有类型 int list 但与输入 int.

我不确定你这行的意思。列表要么是空的，要么有头和尾。（我不知道你为什么认为“第一种情况 [] 不应该是可达的”；列表当然可以是空的。）列表上通常的模式匹配是

match list with
| []       -> …
| hd::tl   -> …

在您的情况下，您不需要任何更复杂的东西。您可以将现有案例用于 [] 和 hd::tl。还有一件事需要更正：你需要在递归调用 find_alpha tl (hd::acc) 中加上括号，因为 find_alpha tl hd::acc 被解析为 (find_alpha tl hd)::acc.

let rec find_alpha (list: int list) (acc: int list) =
   match list with
   |[]       -> acc
   |hd::tl   -> if List.mem hd acc then find_alpha tl acc else find_alpha tl (hd::acc)

由于 hd::tl 情况下的唯一变化是传递给递归调用的第二个参数，我不想重复递归调用。此外，函数不依赖于参数的类型，所以我会让它们保持多态。

let rec find_alpha list acc =
   match list with
   | [] -> acc
   | hd::tl -> find_alpha tl (if List.mem hd acc then acc else hd::acc)

如果您定义一个中间变量，代码可以说更具可读性。

let rec find_alpha list acc =
   match list with
   | [] -> acc
   | hd::tl ->
     let acc' = if List.mem hd acc then acc else hd::acc in
     find_alpha tl acc'

查找 int 列表的不同元素

Finding the different elements of an int list

pattern-matching

ocaml

typechecking