伊德里斯·德克 vs 梅贝

Question

在Idris中用Dec而不是Maybe可以表达什么样的东西？

或者换句话说：什么时候应该选择Dec，什么时候选择Maybe？

Answer 1

我在的回答中略微提到了这一点。使用 Dec:

有两个原因

您想证明事情并从实施中获得更多保证。
您希望您的函数在有限时间内运行。

关于 1。考虑这个函数 Nat 相等：

natEq : (n: Nat) -> (m: Nat) -> Maybe (n = m)
natEq Z Z = Just Refl
natEq Z (S k) = Nothing
natEq (S k) Z = Nothing
natEq (S k) (S j) = case natEq k j of
    Nothing   => Nothing
    Just Refl => Just Refl

您可以为此功能编写测试，看看它是否有效。但是编译器不能在编译时阻止你在任何情况下都写 Nothing 。这样的功能仍然是可编译的。 Maybe 是某种弱证明。这意味着，如果你 return Just 那么你就能找到答案，我们很好，但如果你 return Nothing 就没有任何意义。你就是找不到答案。但是当你使用 Dec 时，你不能只是 return No。因为如果你 returning No 这意味着你实际上可以证明没有答案。因此，将 natEq 重写为 Dec 将需要您作为程序员付出更多努力，但现在的实现更加稳健：

zeroNotSucc : (0 = S k) -> Void
zeroNotSucc Refl impossible

succNotZero : (S k = 0) -> Void
succNotZero Refl impossible

noNatEqRec : (contra : (k = j) -> Void) -> (S k = S j) -> Void
noNatEqRec contra Refl = contra Refl

natEqDec : (n: Nat) -> (m: Nat) -> Dec (n = m)
natEqDec Z Z = Yes Refl
natEqDec Z (S k) = No zeroNotSucc
natEqDec (S k) Z = No succNotZero
natEqDec (S k) (S j) = case natEqDec k j of
    Yes Refl  => Yes Refl
    No contra => No (noNatEqRec contra)

关于 2。 Dec 代表 可判定性 。这意味着您可以 return Dec 仅针对可确定的问题，即可以在有限时间内解决的问题。您可以在有限时间内解决 Nat 等式，因为您最终会遇到 Z 的情况。但是对于一些困难的事情，比如检查给定的 String 是否代表 Idris 计算前 10 个素数的程序，你不能。

伊德里斯·德克 vs 梅贝

Idris Dec vs Maybe

error-handling

theorem-proving

maybe

idris