Рекурсивное использование методов класса типов в Coq

Question

Есть ли способ использовать рекурсию с классами типов Coq? Как, например, при определении шоу для списков, если вы хотите вызвать show функция для списков рекурсивно, тогда вам придется использовать точку фиксирования следующим образом:

Require Import Strings.String.
Require Import Strings.Ascii.

Local Open Scope string_scope.


Class Show (A : Type) : Type :=
  {
    show : A -> string
  }.


Section showNormal.

Instance showList {A : Type} `{Show A} : Show (list A) :=
  {
    show :=
      fix lshow l :=
        match l with
        | nil => "[]"
        | x :: xs => show x ++ " : " ++ lshow xs
        end
  }.

End showNormal.

Что все хорошо, но что если я захочу определить некоторую вспомогательную функцию, которую я буду использовать для определения Show случаи? Как я хочу создать более шоу-функцию DAZZLING под названием magicShow который печатает звезды вокруг чего-то...

Definition magicShow {A : Type} `{Show A} (a : A) : string :=
  "** " ++ show a ++ " **".


Instance showMagicList {A : Type} `{Show A} : Show (list A) :=
  {
    show :=
      fix lshow l :=
        match l with
        | nil => "[]"
        | x :: xs => show x ++ " : " ++ magicShow xs
        end
  }.

Тем не менее, в этом случае Coq не может найти экземпляр шоу для списка xs перейти к magicShow:

Error:
Unable to satisfy the following constraints:
In environment:
A : Type
H : Show A
lshow : list A -> string
l : list A
x : A
xs : list A

?H : "Show (list A)"

Есть ли способ сделать это в целом? То есть, вы можете определить метод для класса типов, используя функции, которые полагаются на экземпляр класса типов, который вы определяете?

Answer 1

Нет, это невозможно сделать. Это работает в Haskell, потому что разрешены произвольные рекурсивные привязки, а язык не заботится о порядке привязок. Coq является более строгим на обоих фронтах. Это имеет смысл, если вы думаете о том, как выглядит десугаринг: рекурсивный вызов show будет ссылаться на определяемый в данный момент экземпляр по имени, но эта привязка еще не находится в области видимости. И вы не можете сделать сам экземпляр фиксированной точкой, потому что вы рекурсивно обращаетесь к структуре типа, а не к значению алгебраического типа данных.

Ваша встроенная точка фиксации работает на show, но проблема становится более сложной, если реализации вашего метода ссылаются друг на друга, такие как

newtype MyInteger = MyInteger Integer

instance Num MyInteger where
  MyInteger m + MyInteger n = MyInteger $ m  + n
  negate (MyInteger m) = MyInteger $ negate m
  m - n = m + negate n
  -- other methods

Здесь звонки (+) а также negate в определении (-) необходимо обратиться к определениям (+) а также negate выше, но это также не работает в Coq. Единственное решение состоит в том, чтобы определить все ваши методы отдельно, вручную ссылаясь друг на друга, а затем определить экземпляр просто установив для каждого метода тот, который вы определили выше. Например,

Inductive MyInteger := Mk_MyInteger : Integer -> MyInteger.

Definition add__MyInteger (m : MyInteger) : MyInteger :=
  let 'Mk_MyInteger m' := m in
  let 'Mk_MyInteger n' := n in
  Mk_MyInteger (add m' n').

Definition negate__MyInteger (m : MyInteger) : MyInteger :=
  let 'Mk_MyInteger m' := m in
  Mk_MyInteger (negate m').

Definition sub__MyInteger (m n : MyInteger) : MyInteger :=
  add__MyInteger m + negate__MyInteger n.

Instance Num__MyInteger : Num MyInteger := {|
  add    := add__MyInteger;
  negate := negate__MyInteger;
  sub    := sub__MyInteger;
  (* other methods *)
|}

Answer 2

Если вы должны это сделать, это можно смоделировать, явно используя конструктор базового Record(поскольку "классы типов - это записи", если цитировать из Software Foundations [1]), которые могут быть созданы с использованием функции (функций), определяемой как фиксированная точка. Я отправлю три примера и объясню, где это может быть полезно.

Опубликованный вами пример можно решить следующим образом (весь код протестирован для Coq 8.10.1):

Require Import Strings.String.

Local Open Scope list_scope.
Local Open Scope string_scope.

Class Show (A : Type) : Type :=
  {
    show : A -> string
  }.

Definition magicShow {A : Type} `{Show A} (a : A) : string :=
  "** " ++ show a ++ " **".

Print Show.
(* Record Show (A : Type) : Type := Build_Show { show : A -> string }
*)
Check Build_Show.
(* Build_Show : forall A : Type, (A -> string) -> Show A *)
Check @magicShow.
(* @magicShow : forall A : Type, Show A -> A -> string *)

Instance showMagicList {A : Type} `{Show A} : Show (list A) :=
  {
    show :=
      fix lshow l :=
        match l with
        | nil => "[]"
        | x :: xs => show x ++ " : " ++ @magicShow _ (@Build_Show _ lshow) xs
        end
  }.

Если вы пытаетесь определить несколько таких методов класса типов, создать экземпляр конструктора записи сложно, но это можно сделать, рассматривая функции, как если бы они были определены посредством взаимной рекурсии (хотя не обязательно должно быть какое-либо фактическое взаимное рекурсия). Вот надуманный пример, гдеShowтеперь есть два метода. Обратите внимание, что экземпляр класса типов добавлен в контекст с анонимнымlet-inпривязка. Очевидно, этого достаточно, чтобы удовлетворить механизм разрешения классов типов Coq.

Require Import Strings.String.

Local Open Scope list_scope.
Local Open Scope string_scope.

Class Show (A : Type) : Type :=
  {
    show1 : A -> string
  ; show2 : A -> string
  }.

Definition magicShow1 {A : Type} `{Show A} (a : A) : string :=
  "** " ++ show1 a ++ " **".

Definition magicShow2 {A : Type} `{Show A} (a : A) : string :=
  "** " ++ show2 a ++ " **".

Fixpoint show1__list {A : Type} `{Show A} (l : list A) : string :=
let _ := (@Build_Show _ show1__list show2__list) in
        match l with
        | nil => "[]"
        | x :: xs => show1 x ++ " : " ++ magicShow1 xs
        end
with show2__list {A : Type} `{Show A} (l : list A) : string :=
let _ := (@Build_Show _ show1__list show2__list) in
        match l with
        | nil => "[]"
        | x :: xs => show1 x ++ " : " ++ magicShow2 xs
        end.

Instance showMagicList {A : Type} `{Show A} : Show (list A) :=
  {
    show1 := show1__list
  ; show2 := show2__list
  }.

Так зачем вам это делать? Хороший пример - определение разрешимого равенства на (розовых) деревьях. В середине определения мы должны рекурсивно апеллировать к разрешимому равенствуlist (tree A). Мы хотели бы использовать вспомогательную функцию стандартной библиотекиCoq.Classes.EquivDec.list_eqdec[2], в котором показано, как передать разрешимое равенство в типеA к list A. посколькуlist_eqdec требуется экземпляр класса типов (тот самый, который мы сейчас определяем), мы должны использовать тот же трюк, что и выше:

Require Import Coq.Classes.EquivDec.
Require Import Coq.Program.Utils.

Set Implicit Arguments.
Generalizable Variables A.

Inductive tree (A : Type) : Type :=
  | leaf : A -> tree A
  | node : list (tree A) -> tree A.

Program Instance tree_eqdec `(eqa : EqDec A eq) : EqDec (tree A) eq :=
 { equiv_dec := fix tequiv t1 t2 :=
    let _ := list_eqdec tequiv in
    match t1, t2 with
    | leaf a1, leaf a2 =>
        if a1 == a2 then in_left else in_right
    | node ts1, node ts2 =>
        if ts1 == ts2 then in_left else in_right
    | _, _ => in_right
    end
}.

Solve Obligations with unfold not, equiv, complement in * ;
  program_simpl ; intuition (discriminate || eauto).

Next Obligation.
  destruct t1;
  destruct t2; 
  ( program_simpl || unfold complement, not, equiv in *; eauto ).
Qed.

Solve Obligations with split; (intros; try unfold complement, equiv ; program_simpl).
(*
No more obligations remaining
tree_eqdec is defined
*)

Комментарий: нет конструктора для создания записи типа EqDec (поскольку он имеет только один метод класса), чтобы убедить Coq в том, что list (tree A) имеет разрешимое равенство, вызов просто list_eqdec tequiv. Для непосвященных,Program здесь просто разрешено заполнить дыры в определении экземпляра позже как Obligations, что удобнее, чем писать соответствующие доказательства inline.