Подкрадывающиеся линзы и CPS за пределами ценового ограничения

Question

Я кодирую форму линз van Laarhoven в OCaml, но у меня возникли трудности из-за ограничения стоимости.

Соответствующий код выглядит следующим образом

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, и возвращает модуль, содержащий значение _1 типа (At * Xt, Bt * Xt, At, Bt) Optic.t. Затем вы можете применить этот функтор к разным модулям, чтобы получить разные экземпляры _1. Например, вы можете написать:

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

Это дает вам значение _1_int типа (int * string, int * string, int, int) Optic.t.

Используйте записи вместо кортежей для представления типов данных, которыми вы хотите управлять с помощью линз. Записи имеют именованные поля, к которым можно получить доступ и обновить с помощью точечной нотации, и они более поддаются полиморфизму, чем кортежи. Например, вы можете написать:

      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 })

Это определяет две линзы, линза_первая и линза_секунда, которые работают с любым типом записи, имеющим первое и второе поле соответственно. Затем вы можете использовать их для управления различными типами записей, не беспокоясь об ограничении значений. Например, вы можете написать:

      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 } *)