[Agda] Heterogeneous Vectors
Thorsten Altenkirch
txa at Cs.Nott.AC.UK
Sat May 29 13:57:07 CEST 2010
Hi Simon,
indeed, Agda's implementation of universe polymorphism is too picky in
this instance. The only work around seems to be exactly the one you
suggest. Actually, due to the lack of extensionality it may be better
to use
HVec : ∀ {n} → Vec Set n → Set
HVec [] = ⊤
HVec (A ∷ As) = A × HVec As
which is extensionally isomorphic to your solution but avoids using
functions.
Cheers,
Thorsten
On 28 May 2010, at 17:32, Simon Foster wrote:
> Hi,
>
> I'm trying to come up with a flexible implementation of a
> heterogeneous vector, but I'm encountering some problems with
> universe levels. At the moment I am using the following
> representation:
>
> data HVec {a} : (n : ℕ) → (As : Vec (Set a) n) → Set (suc a)
> where
> hnil : HVec zero []
> hcons : ∀ {A : Set a} {k} {As} → A → HVec k As → HVec (suc
> k) (A ∷ As)
>
> This works quite well, except when I want to use it in an inductive
> datatype (such as a typed n-ary expressions), because this leads to
> a data-type whose universe index increases depending on the data-
> type depth. My question is, is there another way of representing
> heterogeneous vectors which doesn't require the type to have a
> higher set index than its encapsulated types? I can achieve a
> similar effect using functions, e.g.
>
> HVec : ∀ {a} → (n : ℕ) → (As : Vec (Set a) n) → Set a
> HVec n As = λ (i : Fin n) → lookup i As
>
> But such a representation is very cumbersome to use. Is there a
> better way using an inductive datatype?
>
> Thanks,
>
> -Si._______________________________________________
> Agda mailing list
> Agda at lists.chalmers.se
> https://lists.chalmers.se/mailman/listinfo/agda
More information about the Agda
mailing list