В Идрисе я могу доказать свободные теоремы, например, единственную (полную) функцию типа `forall t. t -> t` это `id`?

Question

Для достаточно полиморфных типов параметричность может однозначно определять саму функцию (подробности см. В теоремах Вадлера бесплатно!). Например, единственная общая функция с типом forall t. t -> t это тождественная функция id,

Можно ли утверждать и доказывать это в Идрисе? (И если это невозможно доказать внутри Идриса, так ли это?)

Следующее - моя попытка (я знаю, что равенство функций не является примитивным понятием в Idris, поэтому я утверждаю, что любая функция универсального типа 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

Answer 1

Ты не можешь Подобные теоремы ("свободная теорема") следуют из предположения, что типы являются абстрактными, и вы не можете сопоставить их с образцом или каким-либо образом различить их структуру. Но вы не можете внутренне выразить в Идрисе свойство абстрактности для типов. Никакая основная реализация теории типов не делает это возможным. Теория типов в цвете имеет эту особенность, но она очень сложна и не имеет практической реализации.

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