这两个函数有什么区别？

Question

我有两个功能：

let rev_flatten l = 
    List.fold_left (fun acc x -> List.fold_left (fun acc y -> y::acc) acc x) [] l 

类型是val rev_flatten : 'a list list -> 'a list = <fun>

和

let rev_flatten = 
    List.fold_left (fun acc x -> List.fold_left (fun acc y -> y::acc) acc x) [] 

类型是val rev_flatten : '_a list list -> '_a list = <fun>

---

我认为这是相同的功能，在至少相同的功能为什么他们有两种不同的类型？为什么第二个元素的类型为_a？它是什么？

Answer 1

以下划线作为前缀的类型变量告诉我们该变量是弱多态性。弱多态变量只能用于一种类型，但编译器无法推导出确切的类型，因此类型变量带有下划线标记。

当您第一次提供参数时，变量将不再是多态，并且将只能接受单一类型的参数。

通常情况下，函数不是泛化的，但如果它的可能包含可变状态，则标记为弱多态。在你的例子中，这可能是这种情况，因为类型系统不知道List.fold_left是纯粹还是不纯的函数。

编辑： 为什么避免局部应用（ETA膨胀）允许函数（偶数不纯）是多态性？

让我们定义一个函数，每次函数调用时都会增加一个内部计数器并将其打印出来。在这一点，它需要一个函数作为参数，增加后的反抽应用它：

let count f = 
    let inc = ref 0 in 
    (fun x -> inc := !inc + 1; print_int !inc; f x);; 

此功能是多态的：('a -> 'b) -> 'a -> 'b。

接下来，让我们再定义两个函数。理财一周报多态：

let max' = count max;; 
val max' : '_a -> '_a -> '_a = <fun> 

和多态之一：

let max'' x = count max x;; 
val max'' : 'a -> 'a -> 'a = <fun> 

现在请注意打印什么，当我们执行这些功能：

max' 1 2;; (* prints 1 *) 
max' 1 2;; (* prints 2 *) 
max' 1 2;; (* prints 3 *) 
max'' 1 2;; (* prints 1 *) 
max'' 1 2;; (* prints 1 *) 
max'' 1 2;; (* prints 1 *) 

所以我们设计为每周多态函数有一个持续可变状态里面允许使用计数器的预期，而多态功能是无状态，并且每次调用都重构，尽管我们想要在里面有一个可变变量。

。这是一个编译器更喜欢可与任何单一类型的，而不是支承全面多态性可以使用弱多态函数的原因。

Answer 2

类型为'_a list list -> '_a list的函数是弱多态的。这意味着，如果你调用一个int list list第二个，rev_flatten将'_a list list -> 'a list但int list list -> int list

不再您可以在这里阅读更多关于为什么这里的细节： http://caml.inria.fr/resources/doc/faq/core.en.html

干杯，

Scott

Answer 3

这仅仅是ML-样式值限制。以前的回答由gasche提供了一些很好的参考文献：What is the difference between 'a and '_l?。

一般来说ML系列适用于简单的语法测试，看看它是否是安全的，完全概括，那就是，做一个类型完全多态性。如果你概括了一个不安全的情况，程序就会有未定义的行为（它可能会崩溃或得到错误的答案）。所以你只有在安全的时候才需要做。

句法规则被应用，因为它的（相对）容易记住。一个更复杂的规则已经尝试了一段时间，但它造成了更多的伤害而不是好的（是普遍的结论）。对ML家族的历史描述将比我更好地解释它。

您的其中一个的功能（第二个）被定义为表达式，即，作为函数的应用程序。根据价值限制，这不是“安全”的。 （请记住，它只是一个语法测试。）第一个是lambda（fun x - > expr）。这是“安全”的。

这就是所谓的价值限制，因为它认为值是安全的。函数应用程序不是（语法）值。 lambda是一个语法值。像[]就是一个值。类似ref []不是一个值。