Coq - возвращаемое значение типа, которое равно возвращаемому типу функции

Question

По некоторой теореме мы знаем, что тип A равен типу B. Как я могу сказать это компилятору Coq во время проверки типа?

Я хочу реализовать непустое дерево, чтобы каждый узел знал свой размер:

Inductive Struct: positive -> Type :=
| Leaf : Struct 1%positive
| Inner: forall {n m}, Struct n -> Struct m -> Struct (n + m).

Я хочу создать функцию, которая генерирует дерево с заданным размером логарифмической глубины. Э.Г.

7 -> 6 + 1 -> (3 + 3) + 1 -> ((2 + 1) + (2 + 1)) + 1 -> (((1 + 1) + 1) + ((1 + 1) + 1)) + 1

Fixpoint nat2struct n : (Struct n) :=
  match n with
  | xH => Leaf
  | xO n => Inner (nat2struct n) (nat2struct n) 
  | xI n => Inner Leaf (Inner (nat2struct n) (nat2struct n))
  end.

Однако я получаю сообщение об ошибке:

Термин "Внутренний лист (Inner (nat2struct n0) (nat2struct n0))" имеет тип "Struct (1 + (n0 + n0))", в то время как ожидается, что он будет иметь тип "Struct n0 ~ 1".

Как я могу это исправить? Мы знаем это (1 + n + n) = xI n, но Кок нет. Если я сформулирую эту теорему раньше, она ничего не изменит:

Theorem nBy2p1: forall n, Pos.add 1%positive (n + n) = xI n. Proof. Admitted.
Hint Resolve nBy2p1.

Есть ли какие-то подсказки, чтобы Coq знал об этой теореме?

PS1: эта теорема уже доказана в стандартной библиотеке? Я не нашел один.

PS2: Я действительно хочу разделить более естественно: 7 -> 4 + 3 -> (2 + 2) + (2 + 1) -> ((1 + 1) + (1 + 1)) + ((1 + 1) + 1). Является ли это возможным? Я не знаю, как написать это так, чтобы Coq понимал, что функция сходится.

Answer 1

При проверке типов Coq использует более слабую форму равенства (иногда называемую равенством определений, суждений или вычислений).В отличие от пропозиционального равенства (с которым «=» связывается по умолчанию), дефиниционное равенство разрешимо.Coq может взять любые два условия и решить, можно ли преобразовать одно в другое.Если бы при проверке типов было разрешено пропозициональное равенство, проверка типов больше не была бы решаема ¹ .

Чтобы решить вашу проблему (и это довольно большая проблема), у вас есть несколько вариантов.

Сделать Struct запись

Я продемонстрирую принцип, используя списки.Во-первых, у нас есть понятие нестандартных списков.

Inductive UnsizedList (A: Type) :=
| unil
| ucons (a: A) (u: UnsizedList A).

Arguments unil [A], A.
Arguments ucons [A] a u, A a u.

Fixpoint length {A: Type} (u: UnsizedList A) :=
match u with
| unil => 0
| ucons _ u' => S (length u')
end.

Мы также можем определить размерный список, где каждый элемент SizedList A n имеет длину n.

Inductive SizedList (A: Type): nat -> Type :=
| snil: SizedList A 0
| scons {n: nat} (a: A) (u: SizedList A n): SizedList A (S n).

ЭтоОпределение сталкивается с той же проблемой, что и ваша.Например, если вы хотите показать, что конкатенация ассоциативна, вы не можете просто доказать concat (concat u v) w = concat u (concat v w), так как две стороны равенства имеют разные типы ((i + j) + k против i + (j + k)).Если бы мы могли просто сказать Coq, какого размера мы ожидаем, что список будет, а затем доказать это позже, мы могли бы решить это.Это то, что делает это определение, которое объединяет UnsizedList с доказательством того, что этот список имеет желаемую длину.

Record SizedListPr (A: Type) (n: nat): Type := {
  list: UnsizedList A;
  list_len_eq: length list = n;
}.

Теперь мы можем иметь concat (concat u v) w = concat u (concat v w);нам просто нужно доказать, что обе стороны имеют длину (i + j) + k.

Использовать принуждения

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

Позвольте мне определить вид принуждения, который отображает элементы типа P x на элементы типа P y, если x = y. ²

Definition coercion {A: Type} (P: A -> Type) {x y: A} (p: x = y): P x -> P y :=
match p with
| eq_refl => fun t => t
end.

Здесь мыиспользуйте индукцию на срок p: x = y.Принцип индукции говорит, по сути, что если мы можем что-то доказать, когда x и y определенно равны, то мы можем доказать это, когда они пропозиционально равны. ³ Когда P x и P y одинаковы, мы можем просто использовать функцию тождества.

Теперь, например, оператор ассоциативности конкатенации для списков с размерами равен concat (concat u v) w = coercion (SizedList A) (add_assoc) (concat u (concat v w)).Таким образом, мы приводим что-то типа SizedList A (i + (j + k)) к чему-то типа SizedList A ((i + j) + k), используя равенство add_assoc: i + (j + k) = (i + j) + k (я упустил некоторые параметры для удобочитаемости).

---

Какой выбор вы делаете, довы.Обсуждение этой проблемы и связанных с ней проблем, а также некоторые дополнительные решения можно найти в Сертифицированном программировании с зависимыми типами страница Равенство .

---

¹ См. теория экстенсиональных типов для класса теорий, где это обычно происходит. Тезис Мартина Хофманна содержит обзор различий между интенциональными и экстенсиональными теориями.

² Если вы знакомы с теорией гомотопических типов, это transport.

³ В этом утверждении достаточно предостережений, что различия между пропозициональным и дефиниционным равенством все еще существуют.

Answer 2

Исходя из ответа пользователя, это решение, которое я выбрал:

Inductive Struct: positive -> Type :=
| Leaf : Struct 1
| Inner : forall {lsize rsize size}
    (proof: Pos.add lsize rsize = size),
    (Struct lsize) -> (Struct rsize) -> Struct size.

Local Lemma nBy2: forall {n}, Pos.add n n = xO n.
Proof.
intros.
assert (Zpos (n + n) = Zpos (n~0)). { rewrite Pos2Z.inj_add. rewrite Z.add_diag. symmetry. apply Pos2Z.inj_xO. }
inversion H. auto.
Qed.

Local Lemma nBy2p1: forall {n}, Pos.add 1 (xO n) = xI n.
Proof.
intros. simpl.
assert (Zpos (1 + n~0) = Zpos (n~1)). { rewrite Pos2Z.inj_add. reflexivity. }
inversion H. auto.
Qed.

Fixpoint structCreate (size : positive) : (Struct size) :=
  match size with
  | xH => Leaf
  | xO n =>
    let child := structCreate n in
    Inner nBy2 child child
  | xI n => 
    let child := structCreate n in
    Inner nBy2p1 Leaf (Inner nBy2 child child)
  end.