[Agda] Proving _!_ is inverse of tabulate...

gallais at ensl.org guillaume.allais at ens-lyon.org
Mon Apr 11 10:58:59 CEST 2011


My guess is that you must begin by pattern matching on [n] because
if n = 0 then [Fin n] has no inhabitant.

--
gallais



On 11 April 2011 08:58, Jason Dusek <jason.dusek at gmail.com> wrote:
> 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