Idris 中简单的句法平等

Question

有没有一种简单的方法可以为数据类型编写相等 (DecEq) 实例？例如，我希望以下内容在其 DecEq 声明中包含 O(n) 行，其中 ?p 很简单：

data Foo = A | B | C | D

instance [syntactic] DecEq Foo where
   decEq A A = Yes Refl
   decEq B B = Yes Refl
   decEq C C = Yes Refl
   decEq D D = Yes Refl
   decEq _ _ = No ?p

Answer 1

David Christiansen 正在研究一些东西来使它总体上自动化，他基本上已经完成了；它可以在 his GitHub repository 中找到。同时，在这种情况下，这里有一种方法可以让您从 O(n^2) 个案例变成 O(n) 个案例。首先，一些预备知识。如果你有一些具有可判定相等性的东西，并且你有一个从你选择的类型到那个类型的注入，那么你可以为那个类型做一个决定过程：

IsInjection : (a -> b) -> Type
IsInjection {a} f = (x,y : a) -> f x = f y -> x = y

decEqInj : DecEq d => (tToDec : t -> d) ->
                      (isInj : IsInjection tToDec) ->
                      (p, q : t) -> Dec (p = q)
decEqInj tToDec isInj p q with (decEq (tToDec p) (tToDec q))
  | (Yes prf) = Yes (isInj p q prf) 
  | (No contra) = No (\pq => contra (cong pq))

不幸的是，直接证明你的函数是一个注入会让你回到 O(n^2) 的情况，但通常情况下任何具有撤回的函数都是单射的：

retrInj : (f : d -> t) -> (g : t -> d) ->
          ((x : t) -> f (g x) = x) ->
          IsInjection g
retrInj f g prf x y gxgy =
  let fgxfgy = cong {f} gxgy
      foo = sym $ prf x
      bar = prf y
  in trans foo (trans fgxfgy bar)

因此，如果您有一个函数，从您选择的类型到具有可判定相等性的函数并对其进行撤回，那么您的类型具有可判定相等性：

decEqRet : DecEq d => (decToT : d -> t) ->
           (tToDec : t -> d) ->
           (isRet : (x : t) -> decToT (tToDec x) = x) ->
           (p, q : t) -> Dec (p = q)
decEqRet decToT tToDec isRet p q =
  decEqInj tToDec (retrInj decToT tToDec isRet) p q

最后，您可以为您选择的内容编写案例：

data Foo = A | B | C | D

natToFoo : Nat -> Foo
natToFoo Z = A
natToFoo (S Z) = B
natToFoo (S (S Z)) = C
natToFoo _ = D

fooToNat : Foo -> Nat 
fooToNat A = 0
fooToNat B = 1
fooToNat C = 2
fooToNat D = 3

fooNatFoo : (x : Foo) -> natToFoo (fooToNat x) = x
fooNatFoo A = Refl
fooNatFoo B = Refl
fooNatFoo C = Refl
fooNatFoo D = Refl

instance DecEq Foo where
  decEq x y = decEqRet natToFoo fooToNat fooNatFoo x y

请注意，虽然 natToFoo 函数的模式有些大，但实际上并没有太多内容。应该可以通过嵌套使图案变小，尽管那样可能很难看。

概括：起初我认为这只适用于特殊情况，但我现在认为它可能比那更好一点。特别是，如果您有一个代数数据类型，其中包含具有可判定相等性的类型，您应该能够将其转换为嵌套 Either 或嵌套 Pair，这将使您到达那里。例如（使用 Maybe 来缩短 Either (Bool, Nat) ()）：

data Fish = Cod Int | Trout Bool Nat | Flounder

watToFish : Either Int (Maybe (Bool, Nat)) -> Fish
watToFish (Left x) = Cod x
watToFish (Right Nothing) = Flounder
watToFish (Right (Just (a, b))) = Trout a b

fishToWat : Fish -> Either Int (Maybe (Bool, Nat))
fishToWat (Cod x) = Left x
fishToWat (Trout x k) = Right (Just (x, k))
fishToWat Flounder = Right Nothing

fishWatFish : (x : Fish) -> watToFish (fishToWat x) = x
fishWatFish (Cod x) = Refl
fishWatFish (Trout x k) = Refl
fishWatFish Flounder = Refl

instance DecEq Fish where
  decEq x y = decEqRet watToFish fishToWat fishWatFish x y

Idris 中简单的句法平等

Easy Syntactic Equality in Idris

idris