rocq-prover / rocq-prover/stdlib
Cannot pattern match on exist in program definitions
Nobody has claimed this yet.
- Dominant language
- Rocq Prover
- Stars
- 42
- Forks
- 38
- Avg merge
- 14h 6m
- Merged PRs (30d)
- 3
Description
Version
Coq 8.13.2
Operating system
Red Hat Enterprise Linux Workstation 7.4
Description of the problem
It is not possible to pattern match on terms
belonging to the sig type family in the following Program Definitions,
because the witnesses seem to get projected out by some hidden coercion.
However, changing sig into sigT or Ssig will allow
implementing the inspect pattern just fine.
From Coq Require Import Lia Logic.StrictProp NArith.NArith.
Obligation Tactic := idtac.
Section Context.
Import N.
Local Open Scope N_scope.
Context (f : N -> N) (mono : forall (a b : N) (l : a < b), f a < f b).
Print Coercions.
Fail Program Definition f_inspect (n : N) : positive :=
let m := f (succ n) - f n in
match exist _ m (eq_refl m) with
| exist _ N0 e => _
| exist _ (Npos p) e => p
end.
Fail Program Definition f_inspect (n : N) : positive :=
let m := f (succ n) - f n in
match exist _ m (eq_refl m) in sig _ return positive with
| exist _ N0 e => _
| exist _ (Npos p) e => p
end.
Program Definition f_inspect (n : N) : positive :=
let m := f (succ n) - f n in
match existT _ m (eq_refl m) in sigT _ return positive with
| existT _ N0 e => _
| existT _ (Npos p) e => p
end.
Next Obligation. intros n m _ _ e. pose proof mono n (succ n) as l. lia. Qed.
Program Definition f_inspect' (n : N) : positive :=
let m := f (succ n) - f n in
match Sexists (fun n : N => Squash (m = n)) m (squash (eq_refl m)) in
Ssig _ return positive with
| Sexists _ N0 e => _
| Sexists _ (Npos p) e => p
end.
Next Obligation.
intros n m _ _ e'.
exfalso. apply sEmpty_ind. induction e' as [e].
pose proof mono n (succ n) as l. lia. Qed.
End Context.
The command has indeed failed with message:
Found a constructor of inductive type sig while a constructor of N is expected.
The command has indeed failed with message:
Wrong inductive type.
Notes
This may be related to coq/coq#4341 or coq/coq#10877.
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Reproduce the provided Coq 8.13.2 example and compare the failing sig matches with the working sigT and Ssig versions. Read the related issues coq/coq#4341 and coq/coq#10877; done means the sig pattern matches in both shown Program Definitions without the reported errors.
Written by the indexing model from the issue text.
Assessment
- Domain
- compilers
- Issue type
- Bug
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Needs clarification
- Newbie friendliness
- 25/100