2017-05-21 11 views
1

m'a donné une solution au théorème suivant comme indiqué ci-dessous:Coq ne génère pas l'hypothèse d'induction

Require Import Coq.Lists.List. 
Import ListNotations. 

Inductive suffix {X : Type} : list X -> list X -> Prop := 
    | suffix_end : forall xs, 
      suffix xs xs 
    | suffix_step : forall x xs ys, 
      suffix xs ys -> 
      suffix (x :: xs) ys. 

Theorem suffix_app (X: Type) (xs ys: list X) : 
    suffix xs ys -> exists ws, xs = ws ++ ys. 
Proof. 
    induction 1 as [|x xsp ysp hs [zs zeq]]. 
    - exists []. reflexivity. 
    - now exists (x :: zs); rewrite zeq. 
Qed. 

je tente de reproduire rapidement sur une autre machine et a tenté ainsi:

Theorem suffix_app (X: Type) (xs ys: list X) : 
    suffix xs ys -> exists ws, xs = ws ++ ys. 
Proof. 
    induction 1. 
    - exists []. reflexivity. 
    - (* Stuck here! *) 
Abort. 

c'est-à-dire sans la clause "as". Cependant, je suis coincé à cause de l'équivalent auto-nommé de "zeq" qui n'est pas généré pour des raisons que je ne peux pas résoudre. Pourquoi l'équivalent (nommé automatiquement) de "zeq" généré par Coq dans le second cas ici?

+2

Il est là pour moi, notez que dans votre premier exemple vous avez eu un 'destruct' dans le motif. Ainsi 'détruire IHsuffix en tant que [zs zeq] .' vous ramènera en jeu. – ejgallego

+0

Je suis choqué de n'avoir jamais vu ça mais ... c'est la vie. Merci, cela répond complètement à ma question. N'hésitez pas à le mettre comme réponse et je l'accepterai. –

+0

Outre la destruction, 'intros' peut aussi faire des réécritures (' -> '):' induction 1 as [| x? ? ? [zs ->]]; [existe [] | existe (x :: zs)]; trivial. » –

Répondre

2

Comme mentionné dans un commentaire @ejgallego c'est parce que la clause as permet de soi-disant motifs d'introduction (qui est des motifs que vous pouvez utiliser avec la tactique intros, comme mentionné par @AntonTrunov dans un commentaire). Le motif [zs zeq] signifie destruct ... as [zs zeq]. Pour en savoir plus sur les intro-patterns, référez-vous à https://coq.inria.fr/refman/Reference-Manual010.html#hevea_default564