4

I noticed that I keep redefining very similar induction principles for nested (and sometime mutually) inductive types because the one generated automatically by Coq is too weak. Here is a very simplified example:

Require Import Coq.Lists.List.

Inductive T : Set :=
| C1 : T
| C2 : list T -> T.

Section T_nested_ind.
  Variable P : T -> Prop.
  Hypothesis C1_case : P C1.
  Hypothesis C2_case : forall l : list T, Forall P l -> P (C2 l).

  Fixpoint T_nested_ind (t : T) :=
    match t with
    | C1 => C1_case
    | C2 xs =>
        let H := (fix fold (xs : list T) : Forall P xs :=
          match xs with
          | nil => Forall_nil _
          | x :: xs => Forall_cons _ (T_nested_ind x) (fold xs)
          end) xs in
        C2_case xs H
    end.
End T_nested_ind.

Coq generates automatically T_ind:

forall P : T -> Prop,
  P C1 ->
  (forall l : list T, P (C2 l)) ->
  forall t : T, P t

While I need an induction hypothesis for the elements nested in the list T_nested_ind:

forall P : T -> Prop,
  P C1 ->
  (forall l : list T, Forall P l -> P (C2 l)) ->
  forall t : T, P t
  1. Is there a way to automate this?
  2. Am I doing something wrong, if I need such an induction principle?
  3. What is the standard solution in Coq?
  4. Is there some incubating research on the subject?
2
  • For 4, I'm curious about what Lean specifically does. In Lean, inductive types are defined in terms of the induction/recursion principles the system generates (as opposed to in Coq, where the primitive is a general fix), so they better by good enough.
    – Tej Chajed
    Commented Nov 3, 2017 at 14:42
  • This is related. You can find some more using Stackoverflow's search facilities: [coq] nested induction. I think you can find some answers on your question (3). Commented Nov 3, 2017 at 15:41

1 Answer 1

3

Here's a partial answer:

  1. No, Coq is giving you an induction principle which is correct but not very useful, and you can do better with a clever use of fix as you already know.
  2. As far as I know, defining and proving a new induction principle is the standard solution.

Not the answer you're looking for? Browse other questions tagged or ask your own question.