[Agda] Need a hand with a proof

Jason -Zhong Sheng- Hu fdhzs2010 at hotmail.com
Wed Dec 18 05:22:45 CET 2019


Hi Jacques,

you just need to generalize over the two fields of the tuple, and then the inductive hypothesis will just work. I think  the reason why it fails by matching on `left-inv (n , xs)`  directly is the direction of the equality. If the function is `x ≡ blah` then the inductive hypothesis seems directly applicable.

     left-inv : (x : Σ ℕ (Vec A)) → (length (toList (proj₂ x)) , fromList (toList (proj₂ x))) ≡ x
     left-inv (0 , [])         = refl
     left-inv (suc n , x ∷ xs)
       with length (toList xs) | fromList (toList xs) | left-inv (n , xs)
     ... | _ | _ | refl = refl


Thanks,
Jason Hu
https://hustmphrrr.github.io/
________________________________
From: Agda <agda-bounces at lists.chalmers.se> on behalf of Jacques Carette <carette at mcmaster.ca>
Sent: December 17, 2019 11:02 PM
To: agda <agda at lists.chalmers.se>
Subject: [Agda] Need a hand with a proof

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) = {!!}

_______________________________________________
Agda mailing list
Agda at lists.chalmers.se
https://lists.chalmers.se/mailman/listinfo/agda
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.chalmers.se/pipermail/agda/attachments/20191218/a889858f/attachment.html>


More information about the Agda mailing list