Techniques for using decision procedures in Idris
This post is a literate Idris file, so first let’s get some bureaucracy out of the way:
module LT 
%default total 
When writing Idris code, we sometimes need a proof as an argument to a function. In many cases, these proofs can be constructed automatically by a decision procedure. Here, I’m using the term "decision procedure" for some property p to refer to a function that returns something in the type Dec p.
An instance of Dec p is either a proof of p or a proof that p is an absurdity. The datatype is defined as follows:
data Dec : Type > Type where 
Yes : p > Dec p 
No : (p > __) > Dec p 
As an example, take the following type from the Idris library that represents a proof that one natural number is less than or equal to another:
data LTE : Nat > Nat > Type where 
lteZero : LTE 0 m 
lteSucc : LTE n m > LTE (S n) (S m) 
The first constructor, lteZero, should be interpreted as an assertion that zero is less than or equal to any natural number. The second, lteSucc, is an assertion that if n≤m, then n+1 ≤ m+1. It happens to be the case that, for any two natural numbers, it is decidable whether the first is less than or equal to the second.
To prove this, we start with two simple lemmas. The first states that it is not the case that the successor of any number is less than or equal to zero:
notLTESZ : LTE (S k) Z > __ 
notLTESZ lteZero impossible 
Additionally, we show that, if k≰j, then k+1 ≰ j+1:
notLTE_S_S : (LTE k j > __) > LTE (S k) (S j) > __ 
notLTE_S_S nope (lteSucc x) = nope x 
We are now in a position to write the decision procedure, by examining each case and using our lemmas to produce the appropriate contents for the No constructor. If the details don’t make sense, then please fire up Idris, replace some righthand sides with metavariables, and examine the proof context.
decLTE : (n,m : Nat) > Dec (n `LTE` m) 
decLTE Z m = Yes lteZero 
decLTE (S k) Z = No notLTESZ 
decLTE (S k) (S j) with (decLTE k j) 
decLTE (S k) (S j)  (Yes prf) = Yes (lteSucc prf) 
decLTE (S k) (S j)  (No contra) = No $ notLTE_S_S contra 
Now that these details are out of the way, we can get to the main point of this blog post: demonstrating various techniques for getting Idris to fill out these proofs for us.
The most straightforward way is to use the interactive editing features to get Idris to construct the proof term directly. For example, if we want to show that 3 ≤ 5, then we need only create a definition with type 3 ‘LTE‘ 5:
ok : 3 `LTE` 5 
We can then use Cc Cs in idrismode to cause it to become
ok : 3 `LTE` 5 
ok = ?ok_rhs 
Using the proof search command Cc Ca on the metavariable gives us
ok : 3 `LTE` 5 
ok = lteSucc (lteSucc (lteSucc lteZero)) 
and the decision procedure simply isn’t necessary. This approach can make our programs ugly, but it is straightforward and direct. We need not actually show the resulting term, however. In Idris, tactic scripts are allowed as the righthand side of definitions. So we can simply invoke the search tactic explicitly, rather than using it through the compiler’s editor interface, and the resulting term does not need to occur in the source file. This can also be more robust in the face of changes to the definition of LTE. The tacticbased definition is:
okTactic : 3 `LTE` 5 
okTactic = proof search 
Here, proof begins a tactic script, and search is the tactic to be invoked.

It cannot solve more "interesting" goals, in which a simple recursive application of constructors is insufficient

It fails to find large goals, as the recursion depth is limited. For example, it cannot solve 103 ‘LTE‘ 105.
One nonsolution is to have the righthand side of the definition perform a case analysis on the result of a call to decLTE, and then return the contents of the Yes case. Because we know that three is, in fact, less than five, we will never need the No case:
okCase : 3 `LTE` 5 
okCase = case decLTE 3 5 of 
Yes prf => prf 
Unfortunately, the Idris compiler needs to be convinced of the fact that No cannot occur. We do this by showing that the No case could cause the empty type to be inhabited, and then use FalseElim. Unfortunately, doing this requires actually proving the property again:
okCase : 3 `LTE` 5 
okCase = case decLTE 3 5 of 
Yes prf => prf 
No nope => FalseElim . nope $ lteSucc (lteSucc (lteSucc lteZero)) 
The next method is to cause the solver for implicit arguments to execute the decision procedure while filling out an implicit argument for the proof, and then return this implicit argument. The definition okImplicit demonstrates this technique:
okImplicit : 103 `LTE` 105 
okImplicit = getProof 
where getProof : {prf : LTE 103 105} > {auto yep : decLTE 103 105 = Yes prf} > 103 `LTE` 105 
getProof {prf} = prf 
All of the work happens in getProof, which is in a where block to keep the type signature of okImplicit clean. In the definition of getProof, the implicit argument prf is the one that will be filled out with the proof, and then returned. The argument yep is an implicit proof that the result of executing the decision procedure will be Yes prf – in other words, that it will succeed, and the thing it succeeds with will unify with prf. The auto keyword causes Idris to fill out the argument with refl, the constructor of proofs of equality.
While the okImplicit technique leads to noisy boilerplate in type signatures, it also tends to cause error messages that are easy to understand. I’ve had a lot of luck using it for embedded DSLs with some kind of side condition (like "these queries must have disjoint schemas").
The final technique that I’d like to demonstrate uses a dependentlytyped extractor of proofs from Dec. The type of the function getYes does caseanalysis on the result of a decision procedure. If the result was Yes, then getYes will return the contents – an instance of p. Otherwise, it returns unit, which contains no interesting information. Note that the result of the case expression is a type — either the type parameter to Dec or the unit type.
getYes : (res : Dec p) > case res of { Yes _ => p ; No _ => () }
The body of getYes performs a case analysis on the result of the decision, either returning a proof or a trivial value, in accordance with the type. Note that Idris’s interactive editing features were able to write this code entirely – the only thing I needed to do was tell it to case split on the argument. Agda, which has more advanced interactive editing features, could probably write the entire body by passing Agsy the c option, which enables case splitting.
getYes (Yes prf) = prf 
getYes (No contra) = () 
Now, getYes can be used on the righthand side of our definition to extract the proof:
okYes : 3 `LTE` 5 
okYes = getYes (decLTE 3 5) 
While this approach is clean, the error messages can be somewhat unpleasant if Idris is asked to prove a falsehood. The following code:
oops : 5 `LTE` 3 
oops = getYes (decLTE 5 3) 
results in this unification error:
When elaborating right hand side of oops: 
Can't unify 
case block in getYes (LTE (fromInteger 5) (fromInteger 3)) (decLTE (fromInteger 5) (fromInteger 3)) (decLTE (fromInteger 5) (fromInteger 3)) 
with 
LTE 5 3 

Specifically: 
Can't unify 
case block in getYes (LTE (fromInteger 5) (fromInteger 3)) (decLTE (fromInteger 5) (fromInteger 3)) (decLTE (fromInteger 5) (fromInteger 3)) 
with 
LTE 5 3 
whereas the error message from
badImplicit : 105 `LTE` 103 
badImplicit = getProof 
where getProof : {prf : LTE 105 103} > {auto yep : decLTE 105 104 = Yes prf} > 105 `LTE` 103 
getProof {prf} = prf 
was
When elaborating right hand side of badImplicit: 
When elaborating argument yep to LT.badImplicit, getProof: 
Can't solve goal 
decLTE (fromInteger 105) (fromInteger 104) = Yes prf 
You have now seen a few ways of getting Idris to find proofs. Hopefully, you’ve also gotten a bit more understanding of how Idris works while compiling your source file.
This post sprang out of a discussion on a Github issue with Nicola Botta. The discussion of error messages is improved as the result of a suggestion from Anthony Cowley. Thanks, Nicola and Anthony!