Isabelle/HOL中如何将类型变量限定为nat或int以定义多变量多项式？

Great question—you’re right that Isabelle doesn’t support that intuitive 'a::nat|int syntax to lock a type variable down to just those two types. Let’s walk through the best ways to get the precise restriction you want, instead of relying on a broader type class like comm_semiring.

Option 1: Build a Custom Type Class for Exactly nat and int #

The cleanest approach here is to create a minimal type class that only nat and int will implement. Here’s how to do it step by step:

First, declare an empty type class (since you don’t need any extra operations beyond what these types already provide):

class nat_or_int =

Next, instantiate this class for both nat and int—this tells Isabelle these are the only types allowed under this constraint:

instantiation nat :: nat_or_int
begin
instance ..
end

instantiation int :: nat_or_int
begin
instance ..
end

Now you can use this class as your type constraint in the polynomial datatype definition:

datatype ('a::nat_or_int) polynomial = Poly "('a × nat list) list"

From now on, any attempt to use a type other than nat or int for 'a will throw a type error—exactly the restriction you’re after.

Option 2: Use a Sum Type for Coefficients #

If you don’t mind adjusting your structure slightly, you could define a sum type that explicitly wraps either nat or int, then use that as your coefficient type directly:

datatype coeff = NatCoeff nat | IntCoeff int

datatype polynomial = Poly "(coeff × nat list) list"

This approach makes the limited coefficient set obvious at a glance. The tradeoff is that you’ll need to pattern-match on NatCoeff or IntCoeff when working with coefficients, but it’s a simple, straightforward solution.

Why Your Initial Syntax Doesn’t Work #

Isabelle’s type class system is built around properties (like being a commutative semiring) rather than enumerating specific types. The 'a::C syntax means "any type that implements class C", so there’s no built-in way to list specific types directly with a | operator. That’s why your first idea didn’t pan out—Isabelle doesn’t interpret that syntax as a type union.

Quick Note on the comm_semiring Fallback #

You mentioned using comm_semiring as an alternative, and while that’s great if you ever want to extend your polynomials to other semiring types, it makes total sense to want a tighter constraint if you only care about nat and int. The custom type class method gives you that precision without unnecessary generality.

内容的提问来源于stack exchange，提问作者Marco