Можно ли кодировать двоичные функции между типами в OCaml?

Мне интересно, можно ли построить нечто похожее на множественную отправку в OCaml. Для этого я попытался сделать явный тип входной сигнатуры мультиметода. В качестве примера я определяю тип числа

type _ num =
| I : int -> int num
| F : float -> float num

Теперь я хотел бы, чтобы функция add суммировала 'a num и a 'b num и возвращала int num, если оба 'a и 'b являются int, а float num, если at по крайней мере, один из них является float. Кроме того, система типов должна знать, какой конструктор будет использовать выход. То есть он должен быть статически известен при вызове функции, что выход имеет тип int num, например.

Это возможно? Пока я могу управлять функцией сигнатуры type a b. a num * b num -> a num, например, чтобы в качестве первого аргумента всегда должен был поставляться (более общий) float. Случай int num * float num должен быть запрещен, что приведет к не исчерпывающим сопоставлениям шаблонов и исключениям времени выполнения.

Кажется, что нужна подпись, например type a b. a num * b num -> c(a,b) num, где c - это функция типа, содержащая правила продвижения типа. Я не думаю, что у OCaml это есть. Разве могут открывать типы или объекты? Я не ищу самую общую функцию между типами, это достаточно, если я могу явно указать несколько комбинаций типов ввода и соответствующий тип вывода.

Ответ 1

Конкретный случай, о котором вы спрашиваете, может быть успешно решён с использованием GADT и полиморфных варианты. См. Вызовы M.add в нижней части этого кода:

type whole = [ `Integer ]
type general = [ whole | `Float ]

type _ num =
  | I : int -> [> whole ] num
  | F : float -> general num

module M :
sig
  val add : ([< general ] as 'a) num -> 'a num -> 'a num

  val to_int : whole num -> int
  val to_float : general num -> float
end =
struct
  let add : type a. a num -> a num -> a num = fun a b ->
    match a, b with
    | I n, I m -> I (n + m)
    | F n, I m -> F (n +. float_of_int m)
    (* Can't allow the typechecker to see an I pattern first. *)
    | _,   F m ->
      match a with
      | I n -> F (float_of_int n +. m)
      | F n -> F (n +. m)

  let to_int : whole num -> int = fun (I n) -> n

  let to_float = function
    | I n -> float_of_int n
    | F n -> n
end

(* Usage. *)
let () =
  M.add (I 1)  (I 2)  |> M.to_int   |> Printf.printf "%i\n";
  M.add (I 1)  (F 2.) |> M.to_float |> Printf.printf "%f\n";
  M.add (F 1.) (I 2)  |> M.to_float |> Printf.printf "%f\n";
  M.add (F 1.) (F 2.) |> M.to_float |> Printf.printf "%f\n"

Что печатает

Вы не можете изменить любой из вышеперечисленных to_float на to_int: он статически что только добавление двух I приводит к I. Однако вы можете изменить to_int до to_float (и отрегулируйте printf). Эти операции легко компилируют и распространяют информацию о типе.

Глупость с вложенным выражением match - это взлом, который я попрошу на список рассылки. Я никогда не видел этого раньше.

Функции общего типа

AFAIK единственный способ оценить общую функцию типа в текущем OCaml требует пользователь должен предоставить свидетеля, то есть некоторую дополнительную информацию о типе и значении. Эта может быть сделано многими способами, например, обертывание аргументов в дополнительных конструкторах (см. ответ @mookid), используя первоклассные модули (также обсуждаемые в следующем раздел), предоставляя небольшой список абстрактных значений на выбор (который реализовать реальную операцию, а оболочка отправляет эти значения). пример ниже использует второй GADT для кодирования конечного отношения:

type _ num =
  | I : int -> int num
  | F : float -> float num

(* Witnesses. *)
type (_, _, _) promotion =
  | II : (int, int, int) promotion
  | IF : (int, float, float) promotion
  | FI : (float, int, float) promotion
  | FF : (float, float, float) promotion

module M :
sig
  val add : ('a, 'b, 'c) promotion -> 'a num -> 'b num -> 'c num
end =
struct
  let add (type a) (type b) (type c)
      (p : (a, b, c) promotion) (a : a num) (b : b num) : c num =
    match p, a, b with
    | II, I n, I m -> I (n + m)
    | IF, I n, F m -> F (float_of_int n +. m)
    | FI, F n, I m -> F (n +. float_of_int m)
    | FF, F n, F m -> F (n +. m)
end

(* Usage. *)
let () =
  M.add II (I 1) (I 2)  |> fun (I n) -> n |> Printf.printf "%i\n";
  M.add IF (I 1) (F 2.) |> fun (F n) -> n |> Printf.printf "%f\n"

Здесь функция типа ('a, 'b, 'c) promotion, где 'a, 'b являются аргументы и 'c - результат. К сожалению, вы должны пройти add экземпляр promotion для 'c, чтобы быть заземленным, то есть что-то вроде этого не будет (AFAIK):

type 'p result = 'c
  constraint 'p = (_, _, 'c) promotion

val add : 'a num -> 'b num -> ('a, 'b, _) promotion result num

Несмотря на то, что 'c полностью определяется 'a и 'b, из-за GADT; компилятор все еще видит, что в основном просто

val add : 'a num -> 'b num -> 'c num

Свидетели действительно не покупают вас, просто имея четыре функции, за исключением того, что набор операций (add, multiply и т.д.) и тип аргумента/результата комбинации, могут быть сделаны в основном ортогональными друг другу; типизация может быть лучше, и вещи могут быть немного проще в использовании и реализации.

EDIT На самом деле можно отказаться от конструкторов I и F, т.е.

val add : ('a, 'b, 'c) promotion -> 'a -> 'b -> `c

Это делает использование намного проще:

M.add IF 1 2. |> Printf.printf "%f\n"

Однако в обоих случаях это не так сложно, как решение полиморфных вариантов GADT +, поскольку свидетель никогда не выведен.

Future OCaml: модульные импликации

Если ваш свидетель является первоклассным модулем, компилятор может выбрать его для вас автоматически с модульными имплицитами. Вы можете попробовать этот код в 4.02.1+modular-implicits-ber. Первый пример просто обертывает свидетелей GADT из предыдущего примера в модулях, чтобы заставить компилятор выбрать их для вас:

module type PROMOTION =
sig
  type a
  type b
  type c
  val promotion : (a, b, c) promotion
end

implicit module Promote_int_int =
struct
  type a = int
  type b = int
  type c = int
  let promotion = II
end

implicit module Promote_int_float =
struct
  type a = int
  type b = float
  type c = float
  let promotion = IF
end

(* Two more like the above. *)

module M' :
sig
  val add : {P : PROMOTION} -> P.a num -> P.b num -> P.c num
end =
struct
  let add {P : PROMOTION} = M.add P.promotion
end

(* Usage. *)
let () =
  M'.add (I 1) (I 2)  |> fun (I n) -> n |> Printf.printf "%i\n";
  M'.add (I 1) (F 2.) |> fun (F n) -> n |> Printf.printf "%f\n"

С модульными implicits вы также можете просто добавлять немаркированные поплавки и ints. Этот пример соответствует отправке функции "свидетель":

module type PROMOTING_ADD =
sig
  type a
  type b
  type c
  val add : a -> b -> c
end

implicit module Add_int_int =
struct
  type a = int
  type b = int
  type c = int
  let add a b = a + b
end

implicit module Add_int_float =
struct
  type a = int
  type b = float
  type c = float
  let add a b = (float_of_int a) +. b
end

(* Two more. *)

module M'' :
sig
  val add : {P : PROMOTING_ADD} -> P.a -> P.b -> P.c
end =
struct
  let add {P : PROMOTING_ADD} = P.add
end

(* Usage. *)
let () =
  M''.add 1 2  |> Printf.printf "%i\n";
  M''.add 1 2. |> Printf.printf "%f\n"

Ответ 2

OCaml, начиная с версии 4.04.0, не имеет способа кодировать зависимости типа на этом уровне. Правила ввода текста должны быть более простыми.

Один из вариантов состоит в том, чтобы использовать для этого простой тип варианта, который переносит все в один (потенциально большой) тип и соответствует:

type vnum =
  | Int of int
  | Float of float

let add_vnum a b =
  match a, b with
  | Int ia, Int ib -> Int (ia + ib)
  | Int i, Float f
  | Float f, Int i -> Float (float_of_int i +. f)
  | Float fa, Float fb -> Float (fa +. fb)

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

type _ gnum =
  | I : int -> int gnum
  | F : float -> float gnum

let add_gnum (type a) (x : a gnum) (y : a gnum) : a gnum =
  match x, y with
  | I ia, I ib -> I (ia + ib)
  | F fa, F fb -> F (fa +. fb)

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

type _ gnum =
  | I : int -> int gnum
  | F : float -> float gnum

let add_gnum' (type a b) (x : a gnum) (y : b gnum) : b gnum =
  match x, y with
  | I i1, I i2 -> I (i1 + i2)
  | F f1, F f2 -> F (f1 +. f2)
  | I i, F f -> F (float_of_int i +. f)
  | F f, I i -> I (int_of_float f + i)

Ответ 3

Один из вариантов заключается в использовании подтипирования с использованием tupling аргументов, что позволяет повторно использовать некоторый код (то, почему используется подтипирование):

type intpair = [`int_int of int * int]
type floatpair = [`float_float of float * float]

type num = [`int of int | `float of float]

type pair =
  [ `float_int of float * int
  | `int_float of int * float
  | intpair | floatpair ]

let plus_int_int = function `int_int (i,j) -> `int (i+j)
let plus_float_float = function `float_float (x,y) -> `float (x+.y)
let plus_int_float = function `int_float (i,y) -> `float(float i +. y)
let plus_float_int = function `float_int (x,j) -> `float(x +. float j)

let plus
  : pair -> num
  = function
    | `int_int _ as a -> plus_int_int a
    | `float_float _ as a -> plus_float_float a
    | `int_float _ as a -> plus_int_float a
    | `float_int _ as a -> plus_float_int a

Теперь, если вы хотите статические гарантии, вам нужно использовать GADT:

type 'a num =
  | Int : int -> int num
  | Float : float -> float num

type 'a binop =
  | Intpair : (int * int) -> int binop
  | Int_Float : (int * float) -> float binop
  | Float_Int : (float * int) -> float binop
  | Floatpair : (float * float) -> float binop

let plus :
  type a . a binop -> a num
  = function
    | Intpair (a,b) -> Int (a+b)
    | Int_Float (a,y) -> Float (float a +. y)
    | Float_Int (x,b) -> Float (x +. float b)
    | Floatpair (x,y) -> Float (x +. y)