[Agda] Proving _!_ is inverse of tabulate...
Jason Dusek
jason.dusek at gmail.com
Fri Apr 8 08:12:22 CEST 2011
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
More information about the Agda
mailing list