OCaml的类型系统的细微之处：多态，pointfree逆转和嵌套列表

Question

如果我定义likeso反向功能：

let reverse = 
    let rec helper out = function 
    | [] -> out 
    | a :: l -> helper (a :: out) l 
    in helper [] 

然后reverse (List.map reverse xs)不类型检查，错误

Error: This expression has type 'a list list 
    but an expression was expected of type 'a list 
    The type variable 'a occurs inside 'a list 

但用明确的参数定义它

let reverse l = 
    let rec helper out = function 
    | [] -> out 
    | a :: l -> helper (a :: out) l 
    in helper [] l 

使事情工作。

这是怎么回事？

Answer 1

你的原始定义：

# let reverse = 
    let rec helper out = function 
     | [] -> out 
     | a :: l -> helper (a :: out) l 
     in helper [];; 
val reverse : '_a list -> '_a list = <fun> 

受到半著名值限制，因为它的应用程序（即，helper []），而不是一个lambda的形式。

第二个定义的形式是lambda，它不受限制。

其他一切都来自于此。

在Stack Overflow上已经多次讨论了数值限制。这里有一个这样的讨论：The value restriction。简短的总结是，在可变值（如引用）存在的情况下，需要对多态类型进行某种限制。价值限制是一种易于记忆的妥协，也不受限制。

当我开始忘记价值限制是什么（周期性地发生）时，我经常参考本文：Jacques Garrigue, Relaxing the Value Restriction