Isabelle 代码生成和线性顺序

Question

我正在尝试使用 export_code 工具进行以下定义：

definition set_to_list :: "('a×'a) set ⇒ ('a×'a) list"
  where "set_to_list A = (SOME L. set L = A)"

由于缺少 Eps 的代码方程，这不起作用。现在发现还有一个定义：

definition sorted_list_of_set :: "'a set ⇒ 'a list" where
  "sorted_list_of_set = folding.F insort []"

但是，我无法断言 ('a ×'a) 是线性顺序（这对我来说没问题，例如，先比较第一个元素，然后再比较第二个元素）。谁能帮我修正我自己的定义或使用现有的定义？

Answer 1

要使用 sorted_list_of_set，您可以为产品类型实施类型 class linorder：

instantiation prod :: (linorder,linorder) linorder begin
definition "less_eq_prod ≡ λ(x1,x2) (y1,y2). x1<y1 ∨ x1=y1 ∧ x2≤y2"
definition "less_prod ≡ λ(x1,x2) (y1,y2). x1<y1 ∨ x1=y1 ∧ x2<y2"
instance by standard (auto simp add: less_eq_prod_def less_prod_def) 
end

您还可以从标准库中导入 "HOL-Library.Product_Lexorder"，其中包含类似的定义。

那么你可以定义set_to_list如果你限制类型参数实现linorder:

definition set_to_list :: "('a::linorder×'a) set ⇒ ('a×'a) list"
  where "set_to_list A = sorted_list_of_set A"

Isabelle 代码生成和线性顺序

Isabelle Code Generation and Linear Order

theorem-proving

isabelle