Agda 中的平等——不相关的争论

Question

我有一个依赖类型，它由一个值加上一些关于它的属性的证明组成。自然地，我希望我关于这种类型的平等概念等同于值组件的平等。这一切都很好，除了我运行在证明这种等式的提升概念的属性时遇到问题（例如这种类型列表上的等式）。

例如：

open import Data.Nat
open import Data.Product
open import Relation.Binary
open import Relation.Binary.PropositionalEquality
open import Relation.Binary.List.Pointwise renaming (Rel to ListRel) hiding (refl)

module Test where

    _≈_ : Rel (ℕ × ℕ) _
    (a₁ , _) ≈ (a₂ , _) = a₁ ≡ a₂

    ≈-sym : Symmetric _≈_
    ≈-sym refl = refl

    ≋-sym : Symmetric (ListRel _≈_)
    ≋-sym = symmetric ≈-sym

在最后一行中，Agda 抱怨它无法解决对中的第二个投影。有趣的是，将最后一行更改为以下 eta 等效表达式意味着它可以解决它们：

    ≋-sym = symmetric (λ {x} {y} → ≈-sym {x} {y})

现在我很自然地知道有时 Agda 无法解决所有隐式参数并且需要一些额外的帮助，但我不明白我通过这样做提供了哪些新信息...

我正在做很多提升平等的工作，我宁愿避免在我的代码中到处添加这些丑陋的 eta 扩展。我想知道是否有人有任何建议可以让类似于原始代码的东西通过？

我已经研究过 irrelevance，但第二个投影用于其他地方，即使它在计算上与相等性无关。

Answer 1

我在猜测，但我认为问题在于隐式参数的顺序对于统一（的一部分）无关紧要。考虑

flipped : (({n m : ℕ} -> n ≡ m) -> ℕ) -> ({m n : ℕ} -> n ≡ m) -> ℕ
flipped k f = k f

这里 k 接收到 {n m : ℕ} -> n ≡ m 类型的东西，而 f 是 {m n : ℕ} -> n ≡ m 类型的（m 在 n 之前），但是Agda 愉快地统一了这两个表达式，因为每个隐式参数在细化过程中都变成了一个元变量，并且元数据不按它们被引入的时间排序——它们按它们被实例化的方式排序（例如，你不能将 α 实例化为 β -> β 然后 β 到 α 因为它会导致 α ≡ α -> α 并且处理这样的循环（称为 equirecursive 类型）是一个不合理的噩梦）。所以当你写

 ≋-sym = symmetric ≈-sym

Agda 很困惑，因为它可能意味着

 ≋-sym = symmetric (λ {x} {y} → ≈-sym {x} {y})
 ≋-sym = symmetric (λ {x} {y} → ≈-sym {y} {x})

（嗯，不完全是，因为第二个表达式类型错误，但 Agda 不会回溯，因此无法解决此类问题）

这与flipped例子不同，因为flipped明确规定了n和m的使用方式，所以

的统一

{n1 m1 : ℕ} -> n1 ≡ m1
{m2 n2 : ℕ} -> n2 ≡ m2

结果为n1 ≡ n2和m1 ≡ m2，问题就解决了。如果你放弃这个规格

unsolved : (({n m : ℕ} -> ℕ) -> ℕ) -> ({m n : ℕ} -> ℕ) -> ℕ
unsolved k f = k f

你会得到未解决的元数据。

您定义的确切问题是 _≈_ 的 RHS 中仅提及对的第一个投影，因此 Agda 不知道如何统一第二个投影。这是一个解决方法：

record Sing {α} {A : Set α} (x : A) : Set where

module Test where

    _≈_ : Rel (ℕ × ℕ) _
    (a₁ , b₁) ≈ (a₂ , b₂) = a₁ ≡ a₂ × Sing (b₁ , b₂)

    ≈-sym : Symmetric _≈_
    ≈-sym (refl , _) = (refl , _)

    ≋-sym : Symmetric (ListRel _≈_)
    ≋-sym = symmetric ≈-sym

Sing是一个虚拟记录，只有一个居民可以自动推断。但是 Sing 允许以推理友好的方式在 _≈_ 的 RHS 中提及 b₁ 和 b₂，这使得 ≋-sym 中的那些元数据可以解决。

尽管如此，(a₁ , b₁) ≈ (a₂ , b₂) = a₁ ≡ a₂ × Sing b₁ 似乎已经给了 Agda 足够的提示如何解决 ≋-sym 中的元数据。

您还可以定义一个模式同义词，使代码稍微好一点：

pattern refl₁ = (refl , _)

≈-sym : Symmetric _≈_
≈-sym refl₁ = refl₁

Agda 中的平等——不相关的争论

Equality in Agda - irrelevant arguments

equality

agda

lifting