Agda, type of proofs and with clause

Question

In AgdaIntro, the view section explains :

..that with doesn’t remember the connection between the with-term and the patterns.

That means when you defines

data   False : Set where
record True  : Set where

isTrue : Bool -> Set
isTrue true  = True
isTrue false = False

infixr 30 _:all:_
data All {A : Set}(P : A -> Set) : List A -> Set where
  all[]   : All P []
  _:all:_ : forall {x xs} -> P x -> All P xs -> All P (x :: xs) 

satisfies : {A : Set} -> (A -> Bool) -> A -> Set
satisfies p x = isTrue (p x)

data Find {A : Set}(p : A -> Bool) : List A -> Set where
  found : (xs : List A)(y : A) -> satisfies p y -> (ys : List A) -> 
           Find p (xs ++ y :: ys)
  not-found : forall {xs} -> All (satisfies (not � p)) xs -> 
              Find p xs

And you want to prove

find1 :{A:Set}(p:A->Bool)(xs:ListA)->Find p xs 
find1 p [] = not-found all []
find1 p(x::xs) with p x
...| true  = found [] x {!!} xs
...| false = {!!}

The type of the hole ({! !}) is isTrue (p x), even though we already matched on p x and found out that it was true.

The compiler is not aware that we did pattern match on p x and asks us for a proof that p x is true !

This motivates the introduction of a new type, the

..type of elements of a type A together with proofs that they are equal to some given x in A.

data Inspect {A : Set}(x : A) : Set where
  it : (y : A) -> x == y -> Inspect x

inspect : {A : Set}(x : A) -> Inspect x
inspect x = it x refl

With this type, the function find can be written :

trueIsTrue : {x : Bool} -> x == true -> isTrue x
trueIsTrue refl = _

falseIsFalse : {x : Bool} -> x == false -> isFalse x
falseIsFalse refl = _

find : {A : Set}(p : A -> Bool)(xs : List A) -> Find p xs
find p [] = not-found all[]
find p (x :: xs) with inspect (p x)
... | it true prf = found [] x (trueIsTrue prf) xs
... | it false prf with find p xs
find p (x :: ._) | it false _   | found xs y py ys =
  found (x :: xs) y py ys
find p (x :: xs) | it false prf | not-found npxs =
  not-found (falseIsFalse prf :all: npxs)

NOW, If I want to prove the following property :

predicate : ∀ {A : Set} {p : A -> Bool } {xs : List A } -> 
            All (satisfies' p) (filter p xs)

I will have the same issue as with find, so I need pattern match on inspect to get a witness, but i ALSO need to have the compiler to progress on filter in the case p x == true !

If I do some parallel pattern matching, the compiler treats them as independent expressions

predicate {A} {p} {xs = []} = all[]
predicate {A} {p} {xs = x :: xs} with p x
predicate {A} {p} {x :: xs} | px with  inspect (p x) 
predicate {A} {p} {x :: xs} | true | it true pf = {!!}
predicate {A} {p} {x :: xs} | true | it false pf = {!!} 
predicate {A} {p} {x :: xs} | false | it true pf = {!!}
predicate {A} {p} {x :: xs} | false | it false pf = {!!}

How can I tell the compiler that the two branches are linked somehow ? Should I add a proof of it ?

user3237465 user3237465 · Accepted Answer · 2014-12-27T13:18:29

Just do not pattern-match on p x:

predicate {A} {p} {xs = []} = all[]
predicate {A} {p} {x :: xs} with inspect (p x) 
predicate {A} {p} {x :: xs} | it true  pf rewrite pf = {!!}
predicate {A} {p} {x :: xs} | it false pf rewrite pf = {!!}

Note, that the inspect idiom is deprecated. Use inspect on steroids. You can find it in the standard library here.

Your code becomes

predicate : ∀ {A : Set} {p : A -> Bool } {xs : List A } -> 
            All (satisfies p) (filter p xs)  
predicate {A} {p} {xs = []} = all[]
predicate {A} {p} {xs = x :: xs} with p x | inspect p x
predicate {A} {p} {x :: xs} | true  | [ pf ] = {!!}
predicate {A} {p} {x :: xs} | false | [ pf ] = {!!}

with pf being in the first hole

.Data.Unit.Core.reveal (.Data.Unit.Core.hide p x) == true

which beta-reduces to p x == true. I.e. if you have

test : ∀ {A : Set} {p : A -> Bool} {x} -> p x == true -> True
test _ = _

then placing test {p = p} pf in the first hole and typing C-c C-d gives you True.

Agda, type of proofs and with clause

1 Answers