OCaml类型不能一概而论

Question

我有以下代码:

type 'v state = {
  visited: string list;
  unvisited: string list;
  value: 'v;}

type ('a,'b) parser =
  | Parser of ('a state -> 'b state list)

type 'a result =
  | Ok of 'a
  | Err

let parseString x = Ok x
let parseInt x = Ok (int_of_string x)
let custom = fun stringToSomething  ->
    Parser (fun { visited; unvisited; value }  ->
            match unvisited with
            | [] -> []
            | next::rest ->
                 (match stringToSomething next with
                  | Ok (nextValue) ->
                      [{
                         visited = (next :: visited);
                         unvisited = rest;
                         value = (value nextValue)
                       }]
                  | Err  -> [])))

let stringp = custom parseString
let intp = custom parseInt

当我尝试编译我的程序时,我收到以下错误custom parseString:

Error: The type of this expression, (string -> '_a, '_a) parser,
         contains type variables that cannot be generalized

这个错误是什么意思？

Answer 1

通用类型变量是可以用任何类型替换的变量.非常规类型变量(也称为弱类型变量)是可以具体化为一种且仅一种类型的变量.通常,当值是可变的或当它是函数应用程序时,会出现弱类型变量.通常,类型泛化只能应用于属于"语法值"类的表达式,其中包括常量,标识符,函数,句法值的元组等.在OCaml中放宽了这个一般规则,如果它们出现在协变位置,也可以推广所有其他表达式的类型变量.为此,类型系统应该看到类型定义并从中推断出协方差(即,类型不应该是抽象的),或者类型变量应该限制为协变类型(即,+在类型定义中作为前缀).

不可通用的类型在模块结构中是可以的,但是它们不能逃避编译单元,因为这会破坏类型的健全性(不同的模块可能将它们具体化为不同的值,并且超出类型系统能力来防止这种情况).由于您的模块不包含.mli文件,因此默认情况下会导出所有内容.

一般来说,有4种方法可以解决这个问题:

1. 创建.mli文件,其中具有非广义类型的值被隐藏或具体化为单形类型;

2. 使用类型约束将类型变量具体化为单形类型;

3. 使用eta-expansion将类型推广,即将值转换为句法函数;

4. 向类型系统证明,通过显示类型变量是协变的,可以放宽值限制.

这些是一般策略.在你的情况下,不可能概括stringp,因为custom parseString不属于一类语法值(它是一个函数应用程序),并且它是一个表达式,其中一个类型变量是逆变的,因为它发生在->类型运算符的左侧.您可以随时询问类型系统,了解类型变量的方差.例如,在不知道任何方差规则的情况下,我们可能会问类型系统:它是真的'a并且'b是协变的.

type (+'a,+'b) parser =
  | Parser of ('a state -> 'b state list)

协方差推理算法将计算以下答案:

The 1st type parameter was expected to be covariant,
       but it is injective contravariant.

从类型系统的角度来看,这意味着stringp作为副作用的定义可以访问类型的值'a(例如,将其存储在缓存存储中),并且在此概括类型变量是不健全的,即,它会导致分段错误.

因此,这里留下的唯一解决方案是将定义扩展为函数,这将保证类型系统每次创建新的解析器时,例如,

let stringp () = custom parseString

或者,或者,不要创建类型解析器的值,而只是为用户提供组合器来创建它们(即custom函数).因此,他们基本上可以在不需要泛化的环境中即时创建它们,例如,

let parse = custom
let string = parseString

let my_parser ... = 
  parse string >> parse char >> ...