我如何在 Idris 中表达范围有效性？

Question

我正在尝试在 Idris 中为一个简单的调查表建模，目前正在努力验证以字符串形式出现的用户输入，w.r.t。到所问问题的类型。

目前我有以下类型：

data Question : Type where
  QCM : {numOptions : Nat}
      -> (question : String) 
      -> (qcmOptions : Vect numOptions String)
      -> (expected : Fin numOptions)
      -> Question

data Answer : (q : Question) -> Type where
   AnswerQCM : (option : Fin n) -> Answer (QCM {numOptions = n } q opts exp)

total 
isCorrectAnswer : (q : Question ) -> Answer q -> Bool
isCorrectAnswer (QCM {numOptions} question qcmOptions expected) (AnswerQCM option) = option == expected


data IsAnswer : (s : String) -> (q : Question) -> Type where
     ValidQCM : (option : Fin n) -> IsAnswer s (QCM {numOptions = n } q opts exp)

notInRange : (num : Fin n) -> { auto prf : GT numOptions n } 
           -> IsAnswer s (QCM {numOptions} q opts exp) -> Void
notInRange num x = ?notInRange_rhs

我不知道如何编写 notInRange函数，它应该证明某些数字可能不是多项选择题调查的有效答案：这个数字应该在正确的范围内问题中提供的选项数量。

更一般地说，我想编写一个 readAnswer 函数，如下所示：

readAnswer : (s : String) -> (q : Question) -> Dec (IsAnswer s q)
readAnswer s (QCM question qcmOptions expected) = ?readAnswer_rhs_1

我似乎很难找到 Dec 的 contra 部分，因为我的类型没有正确表达我想要的约束，以至于其中一些可以被证明无人。

Answer 1

好吧，你的问题的答案是相当大的。你有几个设计问题。我不会只粘贴结果代码。 Intead 我将尝试解释正在发生的事情以及您当前方法中存在的问题。也许我的解决方案并不完全是您想要的（也许您甚至不需要您想要的）但我希望它对您有所帮助。

你的 isCorrectAnswer 函数有一个大问题。它 returns Bool 和 Bool 不利于证明，因为编译器对 Bool 的值知之甚少。如果你想要更多的证明力，你应该使用 Refl 而不是 True/False。 Maybe 和 Dec 的情况相同。如果 Maybe 就足够了，那么可以，但是如果你希望你的实现是可证明的，你应该使用 Dec 而不是 Maybe。一旦你决定在你的函数中使用 Dec，你正在使用和调用的所有函数也应该包含更多可证明的信息。

思考过程的良好开端是考虑具有如下功能：

isCorrectAnswer : (q: Question) -> (a: Answer q) -> expected q = option a

不幸的是，由于两个问题，此功能无法存在。

这是一个证明，证明总是正确的。如果你有任意 Question 和 Answer ，那么预期的答案并不总是正确的。因此，你应该把这个函数转换成属性这样的数据类型。这只是一个通用的方法。
好吧，在当前情况下，您甚至无法为 Question 数据类型编写 expected 函数。也许有人可以，但我尝试过但失败了。此 expected 函数不是您当前实现中相应字段的名称。 numOptions 是 Question 的一些内部事物。如果没有模式匹配，它从外面是不可见的。所以在向量长度上参数化 Question 是件好事。

为了解决问题 2，我将通过以下方式对您的数据类型进行一些转换：

record Question (numOptions : Nat) where
    constructor QCM
    question   : String
    qcmOptions : Vect numOptions String
    expected   : Fin  numOptions

record Answer (q : Question n) where
    constructor AnswerQCM
    option : Fin n

所以现在属性可以看起来像这样：

data IsCorrectAnswer : (q : Question n) -> (a: Answer q) -> Type where
   IsCorrect : {q: Question n} 
            -> {a: Answer q} 
            -> expected q = option a 
            -> IsCorrectAnswer q a

这里是简单的决定程序：

isCorrectAnswer : (q : Question n) -> (a: Answer q) -> Dec (IsCorrectAnswer q a)
isCorrectAnswer (QCM  _ _ expected) (AnswerQCM option) =
    case decEq expected option of
        Yes prf   => Yes (IsCorrect prf)
        No contra => No (\(IsCorrect prf) => contra prf)

在你的问题中，你希望属性在 String 和 Question 之间，而我在 Answer 和 Question 之间实现。所以现在理论上你可以在 qcmOptions 中查找这个字符串，找到 Fin 索引，将它转换为答案并得到 Dec for IsCorrectAnswer。好吧，有点。除了事实证明这是非常非常重要的。只是因为你不能证明你想要的定理的原因。

在您的数据类型中没有 nothing 连接 s: String 和 (option : Fin n)。一些额外的属性和数据类型可能会有所帮助。但更简单的解决方案是使用 Vect 的 Elem property 让您的 IsAnswer 属性包含更多信息。这是最终实现，几乎与 isCorrectAnswer:

相同

data IsAnswer : (s : String) -> (q : Question n) -> Type where
    ValidQCM : {q: Question n} -> Elem s (qcmOptions q) -> IsAnswer s q

readAnswer : (s : String) -> (q: Question n) -> Dec (IsAnswer s q)
readAnswer s (QCM _ options _) = case isElem s options of
    Yes prf   => Yes (ValidQCM prf)
    No contra => No (\(ValidQCM prf) => contra prf)

你会注意到我在这里没有使用 isCorrectAnswer 并且我可能不能因为我之前提到的问题。但我不需要在这里使用它。解决方案越简单越好。

P.S. 对不起，文字墙，我可能写了较短的答案，但我希望这样的答案可以向您澄清更多事情。

我如何在 Idris 中表达范围有效性？

How can I express range validity in Idris?

dependent-type

idris