leanprover / lean4

Lean 4 programming language and theorem prover
https://lean-lang.org
Apache License 2.0
4.65k stars 418 forks source link

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

Open leodemoura opened 1 year ago

leodemoura commented 1 year ago

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
nomeata commented 3 months ago

For mutual, this has been fixed a while ago in #2591.

For nested we are now in a good position to have it, with mutual recursion over nested inductives. @arthur-adjedj said he'd look into this. Thanks!