Zulip Chat Archive

Stream: general

Topic: When does dependent pattern-matching produce HEq?


nrs (Jan 29 2025 at 14:52):

In the code below, refining the match produces a HEq for the hypothesis p stating vec's equality with the pattern, and I'm trying to understand why. Does pattern-matching on indexed families always produce a HEq?

inductive Vect (α : Type) : Nat -> Type
| vnil : Vect α 0
| vcons : (a : α) -> Vect α n -> Vect α n.succ


structure Sig where
  symbol : Type
  arity : symbol -> Nat

example {σ : Sig} : (s : σ.symbol) -> (vec : Vect α (σ.arity s)) ->  n : Nat, n = (σ.arity s) := fun s vec => match h : (σ.arity s), p : vec with
| .zero, .vnil => sorry
| _, .vcons a rest => by trace_state; sorry
/-
α : Type
σ : Sig
s : σ.symbol
vec : Vect α (σ.arity s)
n✝ : Nat
a : α
rest : Vect α n✝
h : σ.arity s = n✝.succ
p : HEq vec (vcons a rest)
⊢ ∃ n, n = n✝.succ
-/

nrs (Jan 29 2025 at 14:55):

Concretely this issue is showing up in the following proof, and I'm trying to avoid HEq as much as possible but I end up using it introduce Vect.Mem.head.

--Context for proof
inductive Vect.Mem : α -> Vect α n -> Prop
| head : (a : α) -> (vec : Vect α n) -> Vect.Mem a (.vcons a vec)
| tail : (b : α) -> Vect.Mem a as -> Vect.Mem a (.vcons b as)

inductive Vect.All : (α -> Prop) -> Vect α n -> Prop
| nil : Vect.All pred .vnil
| cons {p : α -> Prop} : p a -> All p vec -> All p (.vcons a vec)

inductive Ext (σ : Sig) (α : Type)
| mk : (s : σ.symbol) -> Vect α (σ.arity s) -> Ext σ α

abbrev Coalg (σ : Sig) (α : Type) := α -> Ext σ α

inductive isCoalgResultSubtermOf (a : α) (h : Coalg σ α) (x : α) : Prop
| intro : a  (h x).2 -> isCoalgResultSubtermOf a h x

--Proof where I need to reason with HEq

theorem coalgResultsMembershipRelation : (h : Coalg σ α) -> h x = s, vec -> Vect.All (isCoalgResultSubtermOf · h x) vec := sorry

Ultimately, I'm trying to determine to what extent it is possible to completely avoid HEq, to be able to tell when it is absolutely necessary and when I can restructure my code to avoid it.

Kyle Miller (Jan 29 2025 at 16:57):

HEq appears when the types are not defeq

nrs (Jan 29 2025 at 17:46):

thank you for the answer, will be thinking about it


Last updated: May 02 2025 at 03:31 UTC