[Agda] Magic-with and inspect -- can I have both?

Shin-Cheng Mu scm at iis.sinica.edu.tw
Fri Mar 28 05:25:36 CET 2008


Hi,

Assuming that I am proving some property of a function f
that is inductively defined and returns a _⊎_ type :

   f [] = ...
   f (x ∷ xs) with f xs
   ... | inj₁ b = ..
   ... | inj₂ c = inj₂ d

The lemma I am proving mentions

   lemma : {a : Set}(xs : [ a ]) ... ->
              (f xs ≡ inj₂ e) -> ...
   lemma [] .. = ...
   lemma (x ∷ ys)... fx∷ys≡inj₂e ...

At this stage, fx∷ys≡inj₂e has type

        (f (x ∷ ys) | f x) ≡ inj₂ e

For further analysis, one may do a pattern match on f ys:

   lemma : {a : Set}(xs : [ a ]) ... ->
              (f xs ≡ inj₂ e) -> ...
   lemma [] .. = ...
   lemma (x ∷ ys)... fx∷ys≡inj₂e ...
     with f ys
   ...  | inj₁ b = ..
   ...  | inj₂ c = .. { }0

by the magic-with, the type of fx∷ys≡inj₂e at { }0 now gets
refined to:

        inj₂ d ≡ inj₂ e

which I may need in { }0.

However, I may also need to make an inductive call to
lemma, which demands an argument of type f ys ≡ inj₂ c:

   lemma : {a : Set}(xs : [ a ]) ... ->
              (f xs ≡ inj₂ e) -> ...
   lemma [] .. = ...
   lemma (x ∷ ys) ... fx∷ys≡inj₂e ...
     with f ys
   ...  | inj₁ b = ..
   ...  | inj₂ c  with lemma ys ... fys≡inj₂c
   ...     | something = { }0

To produce such a term fys≡inj₂c I need the inspect idiom:

   lemma : {a : Set}(xs : [ a ]) ... ->
              (f xs ≡ inj₂ e) -> ...
   lemma [] .. = ...
   lemma (x ∷ ys) ... fx∷ys≡inj₂e ...
     with inspect (f ys)
   ...  | inj₁ b with-≡ _ = ..
   ...  | inj₂ c with-≡ fys≡inj₂c
           with lemma ys ... fys≡inj₂c
   ...     | something = { }0

But if I do so, magic-with does not work and the type of
fx∷ys≡inj₂e remains to be (f (x ∷ ys) | f x) ≡ inj₂ e
at { }0

How can I have both?

Josh Ko came up with this solution:

   lemma : {a : Set}(xs : [ a ]) ... ->
              (f xs ≡ inj₂ e) -> ...
   lemma [] .. = ...
   lemma (x ∷ ys) ... fx∷ys≡inj₂e ...
     with inspect (f ys)
   ...  | z with-≡ z≡fys with f ys | z≡fys
   ...       | inj₁ b = ..
   ...       | inj₂ c | z≡inj₂ c =
                 with lemma ys ... (≡-trans (≡-sym z≡fys)  
z≡inj₂c)
   ...              | something = { }0


As the name suggests, z≡fys has type z ≡ f ys, while
z ≡ inj₂c has type z ≡ inj₂ c. Composing them together
using transitivity, I get a term having the type I want,
f ys ≡ inj₂ c.

Is there a better way, however? Or, am I on a wrong direction
in the first place if I need properties like this?

sincerely,
Shin



More information about the Agda mailing list