How can I express range validity in Idris?

Question

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 notInRangefunction 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.

Shersh Shersh · Accepted Answer · 2017-03-23T17:28:24

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.

How can I express range validity in Idris?

1 Answers