В Идрисе я могу доказать свободные теоремы, например. единственная (общая) функция типа `forall t. t → t` является `id`?
Для достаточно полиморфных типов параметричность может однозначно определять сама функция (подробнее см. теоремы Вадлера бесплатно!). Например, единственной полной функцией с типом forall t. t -> t является тождественная функция id.
Можно ли утверждать и доказывать это в Идрисе? (И если он не может быть доказан внутри Идриса, это правда?)
Ниже приведена моя попытка (я знаю, что равенство функций не является примитивной концепцией в Идрисе, поэтому я утверждаю, что любая функция родового типа t -> t всегда возвращает тот же результат, что и функция идентификации):
%default total
GenericEndomorphism: Type
GenericEndomorphism = (t: Type) -> (t -> t)
id_is_an_example : GenericEndomorphism
id_is_an_example t = id
id_is_the_only_example : (f : GenericEndomorphism) -> (t : Type) -> (x : t) -> f t x = x
id_is_the_only_example f t x = ?id_is_the_only_example_rhs
Полученное отверстие:
- + Main.id_is_the_only_example_rhs [P]
`-- f : GenericEndomorphism
t : Type
x : t
-------------------------------------------------------
Main.id_is_the_only_example_rhs : f t x = x
Ответы
Ответ 1
Вы не можете. Теоремы, подобные этому ( "свободная теорема" ), следуют из предположения, что типы абстрактны, и вы не можете сопоставить их с ними или каким-либо образом различить их структуру. Но вы не можете внутренне выразить в Идрисе свойство абстрактности для типов. Никакая обычная реализация теории типов не делает этого возможным. Теория типов в цвете имеет эту функцию, но она очень сложна и не имеет практической реализации.
Вы все же можете постулировать бесплатные теоремы и использовать их, но вы должны убедиться, что они не блокируют оценку для вещей, которые вы хотите оценить.
