OCaml 中的类型推断表示我的函数是“a list list -> list”，而它应该是“a list”

Question

我是 OCaml 新手，对函数式编程经验很少。我写了以下函数

let rec reverse l =
  match l with
  | [] -> []
  | h::rest -> (reverse rest) @ h

它应该反转列表中的元素，转换[1;2;3]为[3;2;1]例如。我不知道该函数是否有效，但问题是 OCaml 推断该函数是类型，'a list list -> 'a list而我希望它是'a list -> 'a list.

# reverse [1;2;3;4];;
Error: This expression has type int but an expression was expected of type 'a list

Answer 1

连接运算符@期望其两个操作数都是列表。

当你写下 时 (reverse rest) @ h，它会立即推断出它h一定是一个列表。由于l = h::restandh是一个列表，那么l必定是一个列表的列表。

相反，尝试替换(reverse rest) @ h为(reverse rest) @ [h]. 这应该可以正常工作。

但是，请注意，串联a @ b所需的时间与 的长度成线性关系a。由于您重复调用此串联，因此算法的整体复杂度是二次的。那是非常慢的。如果您使用累加器逐步构建反转列表（使用 only::和 never ） ，实际上可以在线性时间内反转列表@。