潜行镜头和CPS超过了价值限制

Question

我在OCaml中编码了一种van Laarhoven镜头,但由于价值限制我很难.

相关代码如下

module Optic : sig
  type (-'s, +'t, +'a, -'b) t
  val lens : ('s -> 'a) -> ('s -> 'b -> 't) -> ('s, 't, 'a, 'b) t
  val _1 : ('a * 'x, 'b * 'x, 'a, 'b) t
end = struct
  type (-'s, +'t, +'a, -'b) t = 
    { op : 'r . ('a -> ('b -> 'r) -> 'r) -> ('s -> ('t -> 'r) -> 'r) }

  let lens get set =
    let op cont this read = cont (get this) (fun b -> read (set this b))
    in { op }

  let _1 = let build (_, b) a = (a, b) in lens fst build
end

在这里,我代表一个透镜作为较高阶类型,CPS变换功能的变压器('a -> 'b) -> ('s -> 't)(如有人建议在这里讨论在这里).功能lens,fst以及build所有具有完全通用的类型,但它们的组成lens fst build没有.

Error: Signature mismatch:
       ...
       Values do not match:
         val _1 : ('_a * '_b, '_c * '_b, '_a, '_c) t
       is not included in
         val _1 : ('a * 'x, 'b * 'x, 'a, 'b) t

正如要点所示,写作是完全可能的 _1

let _1 = { op = fun cont (a, x) read -> cont a (fun b -> read (b, x)) }

但每次必须手动构建这些镜头是乏味的,使用更高阶函数构建它们会很不错lens.

这里有价值限制吗？

Answer 1

值限制是 OCaml 类型系统的限制，它阻止某些多态值被泛化，即具有在所有类型变量上通用量化的类型。这样做是为了在存在可变引用和副作用的情况下保持类型系统的健全性。

在您的情况下，值限制适用于 _1 值，该值定义为将镜头函数应用于其他两个函数 fst 和 build 的结果。透镜函数是多态的，但它的结果不是，因为它取决于它接收的参数的类型。因此，_1 的类型没有完全泛化，并且无法给出您期望的类型签名。

在这种情况下，有几种可能的方法可以解决值限制：

使用显式类型注释来指定要泛化的类型变量。例如，你可以写：

let _1 : type a b x. (a * x, b * x, a, b) Optic.t = lens fst (fun (_, b) a -> (a, b))

这告诉编译器您想要泛化类型变量 a、b 和 x，并且 _1 的类型应该是一个可以与第一个和第二个组件的任何类型配对的透镜。

使用函子来抽象类型变量并延迟镜头函数的实例化。例如，你可以写：

module MakeLens (A : sig type t end) (B : sig type t end) (X : sig type t end) = struct
   let _1 = lens fst (fun (_, b) a -> (a, b))
end

这定义了一个函子，它采用三个模块作为参数，每个模块定义一个类型 t，并返回一个包含 (At * Xt, Bt * Xt, At, Bt) Optic.t 类型的值 _1 的模块。然后，您可以将此函子应用于不同的模块以获取 _1 的不同实例。例如，你可以写：

module IntLens = MakeLens (struct type t = int end) (struct type t = int end) (struct type t = string end)
let _1_int = IntLens._1

这将为您提供一个 (int * string, int * string, int, int) Optic.t 类型的值 _1_int。

使用记录而不是元组来表示要使用镜头操作的数据类型。记录具有命名字段，可以使用点表示法访问和更新这些字段，并且它们比元组更适合多态性。例如，你可以写：

type ('a, 'x) pair = { first : 'a; second : 'x }
let lens_first = lens (fun p -> p.first) (fun p b -> { p with first = b })
let lens_second = lens (fun p -> p.second) (fun p b -> { p with second = b })

这定义了两个透镜，lens_first 和lens_second，它们分别适用于具有第一和第二字段的任何记录类型。然后，您可以使用它们来操作不同类型的记录，而不必担心值限制。例如，你可以写：

type point = { x : int; y : int }
type person = { name : string; age : int }

let p = { x = 1; y = 2 }
let q = lens_first.op (fun x f -> x + 1) p (fun p -> p)
(* q is { x = 2; y = 2 } *)

let r = { name = "Alice"; age = 25 }
let s = lens_second.op (fun x f -> x + 1) r (fun r -> r)
(* s is { name = "Alice"; age = 26 } *)