Coq: Defining a subtype

2019-05-19 16:28发布

问题:

I have a type, say

Inductive Tt := a | b | c.

What's the easiest and/or best way to define a subtype of it? Suppose I want the subtype to contain only constructors a and b. A way would be to parametrize on a two-element type, e.g. bool:

Definition filt (x:bool): Tt := match x with
  | true => a
  | false => b end.
Check filt true: Tt.

This works but is very awkward if your expression has several (possibly interdependent) subtypes defined this way. Besides, it works only half way, as no subtype is defined. For this I must additionally define e.g.

Notation _Tt := ltac: (let T := type of (forall {x:bool}, filt x) in exact T).
Fail Check a: _Tt. (*The term "filt x" has type "Tt" which should be Set, Prop or Type.*)

which in this case also doesn't work. Another way would be to use type classes, e.g.

Class s_Tt: Type := s: Tt.
Instance a':s_Tt := a.
Instance b':s_Tt := b.
Check a: s_Tt.
Check b': Tt.
Check c: s_Tt.

As you see, this doesn't work: c is still in s_Tt (even if type inference should work better w/ instances). Finally, a coercion

Parameter c0:> bool -> Tt.
Notation a_ := true.
Notation b_ := false.
Notation Tt_ := bool.
Check a_: Tt_.
Check b_: Tt.
Fail Check a: Tt_.

works but, of course, a and b cannot be used as terms of the defined subtype (which would be always convenient and sometimes necessary)

I suppose subset types shouldn't be an answer to this question (a term of a subset type is never that of its (proper) superset). Maybe there's a better way of using type classes for this purpose?