有没有办法重写和简化 `decEq x x`？

Question

在以下代码中（这是尝试解决 'Software Foundations' [列表章节] 中的练习），Idris 报告了 countSingleton_rhs 的一个非常复杂的类型。该类型包括一个复杂的表达式，其核心如下：case decEq x x of ....

module CountSingleton

data NatList : Type where
  Nil : NatList
  (::) : Nat -> NatList -> NatList

-- count occurrences of a value in a list
count : (v : Nat) -> (s : NatList) -> Nat
count _ [] = Z
count Z (Z :: ns) = S (count Z ns)
count Z (_ :: ns) = count Z ns
count j@(S _) (Z :: ns) = count j ns
count (S j) ((S k) :: ns) =
  case decEq j k of
    Yes Refl => S (count (S j) ns)
    No _ => count (S j) ns

-- to prove
countSingleton : (v : Nat) -> (count v [v]) = S Z
countSingleton Z = Refl
countSingleton (S k) = ?countSingleton_rhs

为什么 Idris 不将 decEq x x 简化为 Yes Refl？有没有更好的方法来实现 count 来避免这种行为？我可以对 simplify/rewrite 类型做些什么才能取得进展？

Answer 1

你的计数函数比它需要的更分裂。如果您仍然检查 decEq x y，则可以统一除 count _ [] = Z:

之外的所有情况

count : (v : Nat) -> (s : NatList) -> Nat
count _ [] = Z
count x (y :: ns) = case decEq x y of
    Yes Refl => S (count x ns)
    No _ => count x ns

证明countSingleton的straight-forward方法就是顺其自然。你的 countSingleton_rhs 有一个复杂的类型，因为类型是 case switch，取决于 decEq v v 的结果。使用 with Idris 可以将分支的结果应用于结果类型。

countSingleton : (v : Nat) -> (count v [v]) = S Z
countSingleton v with (decEq v v)
    | Yes prf = Refl
    | No contra = absurd $ contra Refl

如您所见，这似乎有点多余，因为 decEq x x 显然是 Yes Refl。幸运的是，它已经在库中得到证明：decEqSelfIsYes : DecEq a => decEq x x = Yes Refl，我们可以使用它来重写结果类型：

countSingleton : (v : Nat) -> (count v [v]) = S Z
countSingleton v = rewrite decEqSelfIsYes {x=v} in Refl

不幸的是，由于 an open issue，重写 case 类型并不总是有效。但是你可以用 with 重写 count 来规避这个问题：

count : (v : Nat) -> (s : NatList) -> Nat
count _ [] = Z
count x (y :: ns) with (decEq x y)
    | Yes _ = S (count x ns)
    | No _ = count x ns

有没有办法重写和简化 `decEq x x`？

is there a way to rewrite and simplify `decEq x x`?

idris