Почему мое определение не допускается из-за строгой позитивности? - PullRequest
Новая
       54

Почему мое определение не допускается из-за строгой позитивности?

16 голосов
/ 15 мая 2019

У меня есть два следующих определения, которые приводят к двум различным сообщениям об ошибках.Первое определение отклонено из-за строгой позитивности, а второе - из-за несоответствия юниверса. 

(* non-strictly positive *)
Inductive SwitchNSP (A : Type) : Type :=
| switchNSP : SwitchNSP bool -> SwitchNSP A.

Fail Inductive UseSwitchNSP :=
| useSwitchNSP : SwitchNSP UseSwitchNSP -> UseSwitchNSP.

(* universe inconsistency *)
Inductive SwitchNSPI : Type -> Type :=
| switchNSPI : forall A, SwitchNSPI bool -> SwitchNSPI A.

Fail Inductive UseSwitchNSPI :=
| useSwitchNSPI : SwitchNSPI UseSwitchNSPI -> UseSwitchNSPI.

В чате на gitter показано, что сначала проверяются согласованности юниверса (in), то есть первое определение придерживается этогопроверить, но затем не удается из-за строгой проблемы положительности.

Насколько я понимаю, строгое ограничение положительности, если Coq разрешает определения типов данных не строго положительности, я мог бы создавать функции без завершения без использования fix (что довольно плохо).

Чтобы сделать его еще более запутанным, первое определение принято в Агде, а второе дает строгую ошибку положительности. 

data Bool : Set where
  True : Bool
  False : Bool

data SwitchNSP (A : Set) : Set where
  switchNSP : SwitchNSP Bool -> SwitchNSP A

data UseSwitchNSP : Set where
  useSwitchNSP : SwitchNSP UseSwitchNSP -> UseSwitchNSP

data SwitchNSPI : Set -> Set where
  switchNSPI : forall A -> SwitchNSPI Bool -> SwitchNSPI A

data UseSwitchNSPI : Set where
  useSwitchNSP : SwitchNSPI UseSwitchNSPI -> UseSwitchNSPI

Теперьмой вопрос состоит из двух частей: во-первых, какой «злой пример» я мог бы построить с приведенным выше определением?Во-вторых, какое из правил применимо к вышеприведенному определению?

Примечание 1. Думаю, что для пояснения я понимаю, почему второе определение не допускается для проверки типов, нодо сих пор чувствую, что здесь нет ничего «злого», когда определение разрешено.

Примечание 2: Сначала я подумал, что мой пример - это пример этого вопроса , но включающий полиморфизм вселеннойне помогает для второго определения.

...