在枚举上构建荒谬谓词的证明时，有什么技巧可以摆脱样板文件吗？

Question

假设我有

data Fruit = Apple | Banana | Grape | Orange | Lemon | {- many others -}

以及该类型的谓词，

data WineStock : Fruit -> Type where
    CanonicalWine : WineStock Grape
    CiderIsWineToo : WineStock Apple

不适用于 Banana、Orange、Lemon 和其他人。

can be said 这将 WineStock 定义为 Fruit 上的谓词； WineStock Grape 是 true（因为我们可以构建该类型的 value/proof：CanonicalWine）以及 WineStock Apple，但是 WineStock Banana 是 false，因为该类型没有任何 values/proofs.

那么，我怎样才能有效地使用 Not (WineStock Banana)、Not (WineStock Lemon) 等呢？似乎对于 Grape 和 Apple 之外的每个 Fruit 构造函数，我情不自禁地编写了一个在 WineStock 上拆分的案例，在某个地方，充满了 impossibles:

instance Uninhabited (WineStock Banana) where
    uninhabited CanonicalWine impossible
    uninhabited CiderIsWineToo impossible

instance Uninhabited (WineStock Lemon) where
    uninhabited CanonicalWine impossible
    uninhabited CiderIsWineToo impossible

instance Uninhabited (WineStock Orange) where
    uninhabited CanonicalWine impossible
    uninhabited CiderIsWineToo impossible

注意：

代码重复，
当谓词定义增长时，LoC 将爆炸，获得更多的构造函数。想象一下 Not (Sweet Lemon) 证明，假设在 Fruit 定义中有许多不错的选择。

所以，这种方式看起来不太令人满意，几乎不切实际。

还有更优雅的方法吗？

Answer 1

@slcv 是对的：使用计算水果是否满足属性的函数而不是构建各种归纳谓词将使您摆脱这种开销。

这是最小的设置：

data Is : (p : a -> Bool) -> a -> Type where
  Indeed : p x = True -> Is p x

isnt : {auto eqF : p a = False} -> Is p a -> b
isnt {eqF} (Indeed eqT) = case trans (sym eqF) eqT of
                            Refl impossible

Is p x 确保属性 p 持有元素 x （我使用归纳类型而不是类型别名，这样 Idris 就不会展开它在一个洞的上下文中；这样更容易阅读。

只要类型检查器能够自动生成 p a = False 的证明（通过 Refl 或上下文中的假设），

isnt prf 就会驳回虚假证明 prf。

一旦有了这些，您就可以开始定义您的属性，只需枚举阳性案例并添加一个包罗万象的

wineFruit : Fruit -> Bool
wineFruit Grape = True
wineFruit Apple = True
wineFruit _     = False

weaponFruit : Fruit -> Bool
weaponFruit Apple  = True
weaponFruit Orange = True
weaponFruit Lemon  = True
weaponFruit _      = False

您可以将原始谓词定义为使用适当的决策函数调用 Is 的类型别名：

WineStock : Fruit -> Type
WineStock = Is wineFruit

而且，果然，isnt 允许您忽略不可能的情况：

dismiss : WineStock Orange -> Void
dismiss = isnt

在枚举上构建荒谬谓词的证明时，有什么技巧可以摆脱样板文件吗？

Any tricks to get rid of boilerplate when constructing proofs of absurd predicate on enums?

haskell

boilerplate

dependent-type

idris

proof-of-correctness