[Agda] Need a hand with a proof
Jacques Carette
carette at mcmaster.ca
Wed Dec 18 05:02:48 CET 2019
Self-contained code with one hole. The main theorem 'List A ↔ Σ ℕ (Vec
A)' ought to be obvious. Certainly the two functions that witness it
are; the problem is to prove left-inverse. The right-inverse is already
in Data.Vec.Properties. I've tried many ideas, to no avail.
Jacques
module help where
open import Data.List using (List; _∷_; []; length)
open import Data.Vec using (Vec; _∷_; []; fromList; toList)
open import Data.Vec.Properties using (toList∘fromList; ∷-injective)
open import Data.Product using (Σ; _,_; proj₁; proj₂)
open import Function using (_∘_; _↔_; _$_)
open import Relation.Binary.PropositionalEquality
using (_≡_; refl; subst; cong; sym; trans)
private
variable
a : Level
A : Set a
forgetting-length : {a : Level} {A : Set a} → List A ↔ Σ ℕ (Vec A)
forgetting-length = record
{ f = λ xs → length xs , fromList xs
; f⁻¹ = toList ∘ proj₂
; cong₁ = λ { refl → refl }
; cong₂ = λ { refl → refl }
; inverse = left-inv , toList∘fromList
}
where
length-stable : (x : Σ ℕ (Vec A)) → length (toList (proj₂ x)) ≡ proj₁ x
length-stable (0 , []) = refl
length-stable (suc i , x ∷ xs) = cong suc (length-stable (i , xs))
left-inv : (x : Σ ℕ (Vec A)) → (length (toList (proj₂ x)) ,
fromList (toList (proj₂ x))) ≡ x
left-inv (0 , []) = refl
left-inv (suc n , x ∷ xs) = {!!}
More information about the Agda
mailing list