[Agda] RFC: R.B.HeterogeneousEquality + i-cong

Helmut Grohne grohne at cs.uni-bonn.de
Wed Feb 5 08:01:52 CET 2014


Hi,

While using heterogeneous equality from the standard library I found a
need unaddressed. I was unable to cong a Data.Vec.map f to a
heterogeneous equality using the provided toolbox. When looking at the
most relevant tool

cong : ∀ {a b} {A : Set a} {B : A → Set b} {x y}
       (f : (x : A) → B x) → x ≅ y → f x ≅ f y
cong f refl = refl

one can see why usage with Data.Vec failed. The function to be passed,
has to have a single domain type, but the map function has an indexed
domain.

Thus I am proposing the addition of an indexed version of cong to the
standard library. Thus far I have been using the following version:

i-cong : ∀ {l m n} {I : Set l} (X : I → Set m) (Y : I → Set n)
         (f : {i : I} → X i → Y i) {i j : I} → i ≡ j →
         {x : X i} {y : X j} → x ≅ y → f x ≅ f y
i-cong X Y f P.refl refl = refl

It is indexed, but non-dependendent (unlike the original cong). So this
yields the question of whether this is the "right" cong to add, or
whether it should go even further and support both indexing and
dependence.

When using i-cong it is not clear to me whether Y really should remain
and explicit parameter, because it can be inferred in many cases.

Helmut


More information about the Agda mailing list