Можно ли получить свободные теоремы как пропозициональные равенства?

"Свободные теоремы" в смысле бумаги Вадлера "Теоремы бесплатно!" являются уравнениями о некоторых значениях, основанных только на их типе. Так, например,

f : {A : Set} → List A → List A

автоматически удовлетворяет

f . map g = map g . f

Могу ли я взять на себя термин Agda, следующий тип:

(f : {A : Set} → List A → List A) {B C : Set} (g : B → C) (xs : List B)
  → f (map g xs) ≡ map g (f xs)

или если так/если нет, могу ли я сделать что-то более/менее общее?

Я знаю о существовании Lightweight Free Theorems library, но я не думаю, что он делает то, что я хочу (или если он делает, я не понимаю его достаточно хорошо, чтобы это сделать).

(Пример использования - тот, что у меня есть функтор F : Set → Set, и хотел бы доказать, что полиморфная функция F A × F B → F (A × B) автоматически является естественным преобразованием.)

Ответы

Ответ 1

Нет, теория типов, на которой строится Agda, недостаточно сильна, чтобы это доказать. Для этого потребуется функция, называемая "интернализованная параметричность", см. Работу Guilhem:

• Жан-Филипп Бернарди и Гильем Мулен: Вычислительная интерпретация параметричности (2012)
• Guilhem Moulin: Системы чистого типа с теоретикой интернализованной параметричности (2013)

Это позволит вам, например, доказать, что все обитатели "(A: Set) → A → A" равны (полиморфной) тождественной функции. Насколько я знаю, это еще не реализовано ни на одном языке.

Ответ 2

Шанталь Келлер и Марк Лассон разработали тактику для Coq, порождающую отношение параметричности, соответствующее (закрытому) типу, и доказывая, что жители этого типа удовлетворяют порожденному соотношению. Вы можете найти более подробную информацию об этой работе на веб-сайте Keller.

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