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

gallais at ensl.org guillaume.allais at ens-lyon.org
Fri Apr 8 09:09:30 CEST 2011


Hi Jason,

Have you tried to destruct the proofs of [x == y] and [xs == ys] ?

Cheers,

--
guillaume



On 8 April 2011 08:12, Jason Dusek <jason.dusek at gmail.com> wrote:
>  This is a homework problem from a well known tutorial; so I am
>  just going to ask for a clue.
>
>  We would like to show that tabulating the operation of
>  indexing into a vector over the range of indices of the vector
>  is the identity. Some signatures:
>
>    _!_      : {n : ℕ}{A : Set} → Vec A n → Fin n → A
>    tabulate : {n : ℕ}{A : Set} → (Fin n → A) → Vec A n
>
>  In the case where n : ℕ ≡ 0, I can just use refl; tabulating
>  an empty vector is the empty vector. In the non-empty case I
>  am vexed because I would like prove it like this:
>
>  .  Show that the heads of the vector and its tabulation (bound
>    via `with') are equal.
>
>  .  Recurse to find equality of the tails.
>
>  I am not sure how to do this in practice, though; I end up
>  with two statements of refl-ness. Calling the vector and its
>  tabulation x ∷ xs and y ∷ ys, respectively, I have:
>
>    x ≡ y
>    xs ≡ ys
>
>  But I need some transitivity to show that x ∷ xs ≡ y ∷ ys and
>  I am honestly not sure how to do it.
>
>  Of course, I welcome any discussion of alternate approaches to
>  this problem.
>
> --
> Jason Dusek
> ()  ascii ribbon campaign - against html e-mail
> /\  www.asciiribbon.org   - against proprietary attachments
> _______________________________________________
> Agda mailing list
> Agda at lists.chalmers.se
> https://lists.chalmers.se/mailman/listinfo/agda
>


More information about the Agda mailing list