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

OCaml 类型检查器总是为实现推断最佳可能类型（（除了 GADT、高级多态性和第一个 class 模块等高级功能之外））。

因此，如果函数的推断类型与您的预期不符，则意味着您的实现存在错误。

这里的问题是(@)的类型是'a list -> 'a list -> 'a list。因此 reverse rest @ h 意味着：

因此，reverse的类型是'b list list -> 'b list。

Answer 2

串联运算符 @ 期望它的两个操作数都是列表。

当你写(reverse rest) @ h时，立即推断出h一定是一个列表。由于 l = h::rest 和 h 是一个列表，因此 l 必须是列表的列表。

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

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

type inference in OCaml says my function is 'a list list -> list while it should be 'a list