[Agda] Proving _!_ is inverse of tabulate...
Jason Dusek
jason.dusek at gmail.com
Mon Apr 11 08:58:55 CEST 2011
On Fri, Apr 8, 2011 at 08:00, gallais @ ensl.org
<guillaume.allais at ens-lyon.org> wrote:
> Well, propositional equality is an inductive type with only one
> constructor [refl]. So you can pattern match on any term that is of
> the shape [A == B], this will yeld [refl] but also identify the
> corresponding terms.
>
> Let's say that I want to prove that the equality is commutative:
>
> eq-comm : {A : Set} (x y : A) -> x == y -> y == x
> eq-comm x y H = ?
>
> Then I can pattern-match on [H] (I said « destruct » in the previous
> message) and I get the term:
>
> eq-comm x .x refl = ?
>
> The [y] is now a [.x] (the dotted patterns are the one where the value
> is forced by the context)
> and I can prove my goal (which is now [x == x]) using [refl].
Thank you for your explanation. I now see how to leverage an
existing refl -- it allows me to identify terms in pattern
matches.
Unfortunately, showing that [tabulate (_!_ xs) ≡ xs] still
eludes me. I already have a proof that [tabulate f ! i ≡ f i]
so I could use this to show that the heads of the vectors are
equal, I think; but I'm not sure how to bring it in to scope.
To bring it in scope with a `with' seems not to work at all:
lem-tab-! xs with xs | tabulate (_!_ xs) | lem-!-tab (_!_ xs) zero
...
This fails with:
(suc (_102 xs)) != .n of type ℕ
when checking that the expression zero has type Fin .n
I hate to simply reprint the exercize and a solution here; the
tutorial does not seem to offer much guidance here, though.
--
Jason Dusek
() ascii ribbon campaign - against html e-mail
/\ www.asciiribbon.org - against proprietary attachments
More information about the Agda
mailing list