Idris proved by definition
I can write a function
powApply : Nat -> (a -> a) -> a -> a
powApply Z f = id
powApply (S k) f = f . powApply k f
and it's trivial to prove:
powApplyZero : (f : _) -> (x : _) -> powApp Z f x = x
powApplyZero f x = Refl
So far so good. I am now trying to generalize this function to work with negative metrics. Of course, the opposite should be true:
import Data.ZZ
-- Two functions, f and g, with a proof that g is an inverse of f
data Invertible : Type -> Type -> Type where
MkInvertible : (f : a -> b) -> (g : b -> a) ->
((x : _) -> g (f x) = x) -> Invertible a b
powApplyI : ZZ -> Invertible a a -> a -> a
powApplyI (Pos Z) (MkInvertible f g x) = id
powApplyI (Pos (S k)) (MkInvertible f g x) =
f . powApplyI (Pos k) (MkInvertible f g x)
powApplyI (NegS Z) (MkInvertible f g x) = g
powApplyI (NegS (S k)) (MkInvertible f g x) =
g . powApplyI (NegS k) (MkInvertible f g x)
Then I'll try to prove a similar statement:
powApplyIZero : (i : _) -> (x : _) -> powApplyI (Pos Z) i x = x
powApplyIZero i x = ?powApplyIZero_rhs
However, Idris refuses to evaluate the application powApplyI
, leaving the type ?powApplyIZero_rhs
as powApplyI (Pos 0) i x = x
(yes, Z
changed to 0
). I've tried writing powApplyI
in a dotless style and defining my own ZZ
with a modifier %elim
(which I don't understand), but none of them worked. Why isn't the proof checked by checking the first case powApplyI
?
Idris Version: 0.9.15.1
Here are some things:
powApplyNI : Nat -> Invertible a a -> a -> a
powApplyNI Z (MkInvertible f g x) = id
powApplyNI (S k) (MkInvertible f g x) = f . powApplyNI k (MkInvertible f g x)
powApplyNIZero : (i : _) -> (x : _) -> powApplyNI 0 i x = x
powApplyNIZero (MkInvertible f g y) x = Refl
powApplyZF : ZZ -> (a -> a) -> a -> a
powApplyZF (Pos Z) f = id
powApplyZF (Pos (S k)) f = f . powApplyZF (Pos k) f
powApplyZF (NegS Z) f = f
powApplyZF (NegS (S k)) f = f . powApplyZF (NegS k) f
powApplyZFZero : (f : _) -> (x : _) -> powApplyZF 0 f x = x
powApplyZFZero f x = ?powApplyZFZero_rhs
The first proof went well, but ?powApplyZFZero_rhs
stubbornly keeps the class powApplyZF (Pos 0) f x = x
. Clearly there is some problem with ZZ
(or my use of).
source to share
Problem: It powApplyI
wasn't complete enough, according to Idris. The outcome of the Idris integrity check relies on the ability to reduce parameters to structurally smaller shapes and with raw ZZ
s, this will not work.
The answer is to delegate the recursion to the plain old one powApply
(which is proven by all):
total
powApplyI : ZZ -> a <~ a -> a -> a
powApplyI (Pos k) (MkInvertible f g x) = powApply k f
powApplyI (NegS k) (MkInvertible f g x) = powApply (S k) g
Then, if split into the i
case, the powApplyIZero
proof is trivial.
Thanks to Melvar from #idris IRC channel.
source to share
powApplyI (Pos Z) i x
does not diminish further, because it is i
not in a weak normal head shape.
I don't have Idris compiler, so I rewrote your code in Agda. This is pretty similar:
open import Function
open import Relation.Binary.PropositionalEquality
open import Data.Nat
open import Data.Integer
data Invertible : Set -> Set -> Set where
MkInvertible : {a b : Set} (f : a -> b) -> (g : b -> a) ->
(∀ x -> g (f x) ≡ x) -> Invertible a b
powApplyI : {a : Set} -> ℤ -> Invertible a a -> a -> a
powApplyI ( + 0 ) (MkInvertible f g x) = id
powApplyI ( + suc k ) (MkInvertible f g x) = f ∘ powApplyI ( + k ) (MkInvertible f g x)
powApplyI -[1+ 0 ] (MkInvertible f g x) = g
powApplyI -[1+ suc k ] (MkInvertible f g x) = g ∘ powApplyI -[1+ k ] (MkInvertible f g x)
Now you can define your powApplyIZero
as
powApplyIZero : {a : Set} (i : Invertible a a) -> ∀ x -> powApplyI (+ 0) i x ≡ x
powApplyIZero (MkInvertible _ _ _) _ = refl
Pattern matching does not i
cause unification, but powApplyI (+ 0) i x
is replaced by powApplyI (+ 0) i (MkInvertible _ _ _)
, so it powApplyI
can continue.
Or you can write this explicitly:
powApplyIZero : {a : Set} (f : a -> a) (g : a -> a) (p : ∀ x -> g (f x) ≡ x)
-> ∀ x -> powApplyI (+ 0) (MkInvertible f g p) x ≡ x
powApplyIZero _ _ _ _ = refl
source to share