Как определить индуктивный тип, взаимно рекурсивный с функцией?

Я хочу определить индуктивный тип Foo, с конструкторами, принимающими в качестве аргументов некоторые свойства. Я хочу, чтобы эти свойства зависели от индуктивных аргументов того типа, который я сейчас определяю. Я хочу иметь возможность собирать некоторые данные от них внутри этих свойств, используя некоторую рекурсивную функцию bar, которая будет принимать объект типа Foo. Однако я не знаю, как объявить этих двоих, чтобы Coq принял их определения. Я хочу написать что-то вроде этого:

Inductive Foo : Set (* or Type *) :=
| Foo1 : forall f : Foo, bar f = 1 -> Foo
| Foo2 : forall f : Foo,  bar f = 2 -> Foo
| Foon : nat -> Foo
with bar (f : Foo) : nat := 
  match f with
  | Foo1 _ _ => 1
  | Foo2 _ _ => 2
  | Foon n => S n
  end.

Обычно with - это способ обработки взаимной рекурсии, однако все примеры, которые я видел, когда он использовался с обоими определениями, начинаются либо с Inductive, либо с обоими Fixpoint. Возможна ли вообще такая взаимная рекурсия?


person Joald    schedule 27.04.2020    source источник
comment
Наихудшее приходит к худшему, я думаю, вы всегда можете изменить использование такой функции, как bar, в терминах Inductive, представляющих ее график. Однако этот перевод может быть излишним для этой цели.   -  person HTNW    schedule 27.04.2020


Ответы (1)


Этот тип определения известен как «индуктивно-рекурсивный». К сожалению, он не поддерживается в Coq, но, если не ошибаюсь, поддерживается в программе доказательства теорем Agda.

person Arthur Azevedo De Amorim    schedule 27.04.2020