I am trying to model a simple survey form in Idris and currently struggling with validating user input, which comes as a string, w.r.t. to the type of questions asked.
Currently I have the following types:
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
I don't see how to write the notInRange
function which should be a proof that some number may not be a valid answer to a multiple-choice question survey: This number should be in the correct range for the number of options offered within the question.
More generally , I want to write a readAnswer
function that would look like:
readAnswer : (s : String) -> (q : Question) -> Dec (IsAnswer s q)
readAnswer s (QCM question qcmOptions expected) = ?readAnswer_rhs_1
It seems I am having a hard-time finding the contra
part of Dec
because my types do not correctly express the constraints I want in such a way that some of them can be proved uninhabited.
Well, answer to your question is pretty big. You have several design problems. I won't just paste result code. Intead I'll try to explain what's going on and what are problems in your current approach. And maybe my solution is not exactly what you want (and maybe you even don't need exactly what you want) but I hope it helps you.
One big problem is in your isCorrectAnswer
function. It returns Bool
and Bool
is bad for proving because compiler doesn't know much from value of Bool
. If you want more proving power, you should use Refl
instead of True/False
. Same situation with Maybe
and Dec
. If it's enough for you to have Maybe
then ok, but if you want your implementation be provable you should using Dec
instead of Maybe
. And once you're decided to use Dec
in your function, all functions you are using and calling from it should also contain more provable information.
Good start for thinking process is to think about having some function like:
isCorrectAnswer : (q: Question) -> (a: Answer q) -> expected q = option a
Unfortunately, this function can't exist because of two problems.
- It's a proof and proof is what is always true. If you have arbitrary
Question
and Answer
it's not always true that expected answer is exactly that what was given. Thus, you should transform this function into data type with such property. It's just a general approach.
- Well, you can't even write
expected
function for your Question
data type in current situation. Maybe someone can but I tried and failed. This expected
function is not the name of corresponding field in your current implementation. And numOptions
is some internal thing for Question
. It's not visible from outside without pattern matching. So it's good thing to parametrize Question
over vector length.
To solve 2 I'll transform your data types a little in the next way:
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
So now property can look like this:
data IsCorrectAnswer : (q : Question n) -> (a: Answer q) -> Type where
IsCorrect : {q: Question n}
-> {a: Answer q}
-> expected q = option a
-> IsCorrectAnswer q a
And here is simple deciding procedure for it:
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)
In your question you want property between String
and Question
while I implemented between Answer
and Question
. So now theorically you can just lookup this string in qcmOptions
, find Fin
index, transform it to answer and get Dec
for IsCorrectAnswer
. Well, sort of. Except it turns out to be very very non-trivial. Just because of reasons why you can't prove theorem you want.
There is nothing to connect s: String
with (option : Fin n)
in your data type. Probably, several additional properties and data types can help. But simpler solution is to make your IsAnswer
property contain more information using Elem
property for Vect
. And here is final implementation almost identical to 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)
You can notice that I didn't use isCorrectAnswer
here and I probably can't because of problems I've mentioned earlier. But I don't need to use it here. Simpler solution is better.
P.S. Sorry for wall of text, I've may been write shorter answer but I hope in such way this answer can clarify more things to you.