Zulip Chat Archive

Stream: lean4

Topic: Univerally quantified type class expression


Alex Keizer (Jun 23 2022 at 15:15):

I'm working with vectors of things, implemented as maps from a finite index typed, i.e.,

/-- An alternate definition of `fin n` defined as an inductive type instead of a subtype of `Nat`. -/
inductive Fin2 : Nat  Type
  | /-- `0` as a member of `fin (succ n)` (`fin 0` is empty) -/
  fz {n : Nat} : Fin2 (n.succ)
  | /-- `n` as a member of `fin (succ n)` -/
  fs {n : Nat} : Fin2 n  Fin2 (n.succ)
  deriving DecidableEq

abbrev TypeVec (n : Nat) := Fin2 n  (Type _)

Now I want to require that all elements of such a vector implement a typeclass, say Inhabited for a vector of types. Since there are finitely many element in any vector, I want this assumption to be inferred.

-- The compiler accepts a quantified type class
example (v : TypeVec n) [i, Inhabited (v i)] :
  True := by sorry

However, I cannot seem to provide instances for such a quantified statement.
The instances are accepted just fine, but inference does not find them

section
  abbrev VecClass' (v : TypeVec n) :=
   i, Inhabited (v i)

  instance VecInhabited_nil' (v : TypeVec 0) :  i, Inhabited (v i)
    := by intro i; cases i

  instance VecClass_succ'  (v : TypeVec (.succ n))
                              [zero : Inhabited (v .fz)]
                              [succ : VecClass' (fun i => v (.fs i))] :
                           i, Inhabited (v i) :=
  by intro i;
      cases i;
      exact zero;
      apply succ
end

/-- The vector `![Nat, Int]` -/
abbrev v₂ : TypeVec 2
  | .fz     => Nat
  | .fs .fz => Int

-- This fails
example : VecClass' v₂ :=
  by infer_instance

If I take the same idea, but instead box ∀ i, Inhabited (v i) in a new type class, everything works as expected.

section
  /-- A custom type class to express that all elements of `v` implement `Inhabited` -/
  class VecClass (v : TypeVec n) where
    prop :  i, Inhabited (v i)


  instance VecClass_nil (v : TypeVec 0) : VecClass v
    := by intro i; cases i

  instance VecClass_succ  (v : TypeVec (.succ n))
                              [zero : Inhabited (v .fz)]
                              [succ : VecClass (fun i => v i.fs)] :
                          VecClass v :=
  by intro i;
      cases i;
      exact zero;
      apply succ.prop
    
end

-- succeeds
example : VecClass v₂ :=
  by infer_instance

Oddly enough, I can provide an instance for the abbrev version if I defer directly to the boxed version.

section
  instance instUnbox [box : VecClass v] : VecClass' v
   := box.prop

  -- Now it works for the abbreviation as well
  example : VecClass' v₂ :=
    by infer_instance
end

So my direct issue is solved, but I am quite surprised that I need the boxed version. Does anybody have an idea as to what is going on?


Last updated: Dec 20 2023 at 11:08 UTC