Idris：有没有办法在等式证明中引用抽象变量？

Question

问题的最简单示例（但不是我可以展示的唯一示例）是：假设我得到了一个高阶函数 f : (a -> b) -> c。我想证明 f = (\g => f (\x => g x)).

根据我自己的推理，它应该非常简单：只需应用 eta-equivalence 两次（一次在内部，然后在外部）。

如果我想证明 f = (\x => f x)，一个简单的 Refl 就足够了：这让我想到 "Idris knows about eta-equivalence"。但话又说回来，同样的解决方案对 f = (\g => f (\x => g x)).

不起作用

那时，我尝试使用 rewrite，但找不到在 (\g => f (\x => g x)) 中引用 g 的方法：

lemma : {g : a -> b} -> g = (\x => g x)
lemma = Refl

theorem : {f : (a -> b) -> c} ->
          f = (\g => f (\x => g x))
theorem = rewrite (lemma {g = _}) in Refl

但是，当然，伊德里斯无法弄清楚 _ 应该是什么，我也不知道。

当然，这可以进一步简化为证明 (\g => f g) = (\g => f (\x => g x)) 的问题，因为 Idris 知道相等性是可传递的并且知道 eta 等价性（至少当它不是 "hidden" 在 lambda 抽象中).

我开始相信我正在经历的事情正在以某种方式发生，因为 Idris 不知道可扩展性：是否有任何其他方法可以证明这一点（无需调整我正在使用的平等概念，例如如使用 setoids)?

我正在使用来自 git 的 Idris 1.3.2。

Answer 1

你可以假设外延性：

postulate
funext : {f, g : a -> b} -> ((x : a) -> f x = g x) -> f = g

theorem : {f : (a -> b) -> c} -> f = (\g => f (\x => g x))
theorem = funext $ \g => Refl

Idris：有没有办法在等式证明中引用抽象变量？

Idris: Is there a way to reference an abstracted variable in an equality proof?

theorem-proving

idris