pattern matching - Proofs about functions that depend on the ordering of their alternatives -

having quite experience in haskell, started use idris theorem proving. minimal example illustrates problem encountered when trying prove rather simple statements.

consider have total function test:

total test : integer -> integer test 1 = 1 test n = n 

of course see function simplified test n = n, let's prove it. going on cases:

total lemma_test : (n : integer) -> test n = n lemma_test 1 = refl lemma_test n = refl 

but, doesn't type-check:

type mismatch between         n = n (type of refl) ,         test n = n (expected type)  specifically:         type mismatch between                 n         ,                 test n 

so, problem seems idris cannot infer second case of lemma_test n not equal 1 , second case of test must applied.

we can, of course, try explicitly list cases, can cumbersome, or impossible, in case integers:

total lemma_test : (n : integer) -> test n = n lemma_test 1 = refl lemma_test 2 = refl lemma_test 3 = refl ... 

is there way prove statements functions not defined on finite set of data constructors instead depend on fact pattern-matching works top bottom, test in example?

maybe there rather simple solution fail see, considering functions occur quite often.

as others have said, integer primitive, , not inductively defined idris type, therefore can't exhaustive pattern matching on it. more specifically, issue in idris (and in state-of-the-art agda too!) can't prove things "default" pattern matches, because don't carry information previous patterns failed match. in our case, test n = 1 doesn't give evidence n not equal 1.

the usual solution use decidable equality (boolean equality too) instead of fall-through:

import prelude  %default total  test : integer -> integer test n (deceq n 1)   test n | yes p = 1   test n | no  p = n  lemma_test : (n : integer) -> (test n) = n lemma_test n (deceq n 1)  lemma_test _ | (yes refl)  = refl  lemma_test n | (no contra) = refl 

here, no result carries explicit evidence failed match.