lean4 icon indicating copy to clipboard operation
lean4 copied to clipboard

Support for mutual and nested inductive types as `DecidableEq` instance generator

Open leodemoura opened this issue 2 years ago • 1 comments

We currently have to manually write DecidableEq instances for nested and mutual inductive datatypes. Here is an example.

namespace Example

inductive Min where
  | Base
  | Const (a : List Min)

mutual
def decMin (a b : Min) : Decidable (a = b) :=
  match a, b with
  | .Base, .Base         => isTrue rfl
  | .Base, .Const ..     => isFalse (by intro; contradiction)
  | .Const .., .Base     => isFalse (by intro; contradiction)
  | .Const as, .Const bs => match decMinList as bs with
    | isTrue h => isTrue (by rw [h])
    | isFalse _ => isFalse (by intro h; injection h; contradiction)

def decMinList (as bs : List Min) : Decidable (as = bs) :=
  match as, bs with
  | [], [] => isTrue rfl
  | _::_, [] => isFalse (by intro; contradiction)
  | [], _::_ => isFalse (by intro; contradiction)
  | a::as, b::bs =>
    match decMin a b with
    | isTrue h₁ => match decMinList as bs with
      | isTrue h₂ => isTrue (by rw [h₁, h₂])
      | isFalse _ => isFalse (by intro h; injection h; contradiction)
    | isFalse _ => isFalse (by intro h; injection h; contradiction)
end

instance : DecidableEq Min :=
  decMin

leodemoura avatar Jul 17 '23 19:07 leodemoura