如何声明一个 hasEq 约束？

Question

我刚开始使用 F*，我的意思是我已经在教程中写了几行。到目前为止它真的很有趣，我想继续学习。

我尝试自己做的第一件事是编写一个表示非空列表的类型。这是我的尝试：

type nonEmptyList 'a = l : (list 'a) { l <> [] }

但我收到错误

Failed to verify implicit argument: Subtyping check failed; expected type (a#6468:Type{(hasEq a@0)}); got type Type

不过我知道我的方向是正确的，因为如果我将列表类型限制为包含字符串，会起作用：

type nonEmptyList = l : (list string) { l <> [] }

我假设这意味着原始示例中的 l <> [] 无效，因为我没有指定 'a 应该支持相等性。问题是我一辈子都弄不明白该怎么做。我想这与称为 hasEq 的更高类型有关，但尝试诸如：

type nonEmptyList 'a = l : (list 'a) { hasEq 'a /\ l <> [] }

没有带我去任何地方。本教程不涵盖 hasEq，而且我在 GitHub 存储库的示例中找不到任何有用的信息，所以现在我被卡住了。

Answer 1

您正确地确定了这里的问题。您在 nonEmptyList 的定义中使用的类型 'a 未指定，因此无法支持相等性。您的直觉是正确的，您需要告诉 F* 'a 是一个具有相等性的类型，方法是对其进行细化：

为此，您可以编写以下内容：

type nonEmptyList (a:Type{hasEq a}) = l : (list a) { l <> [] }

请注意，我用于该类型的活页夹是 a 而不是 'a。它会导致语法错误，它更有意义，因为它不再是 "any" 类型。另外，请注意，如果需要，您可以更精确地将 a 类型的宇宙指定为 Type0。

Answer 2

你的分析确实正确，采纳的答案大体上给出了正确的解决方案。

不过，对于您的具体示例，您不需要列表元素上的可判定相等性：您可以只使用 (list 'a){ ~ (List.isEmpty l) }.

作为参考，这里是 isEmpty 的定义：

(** [isEmpty l] returns [true] if and only if [l] is empty  *)
val isEmpty: list 'a -> Tot bool
let isEmpty l = match l with
  | [] -> true
  | _ -> false

如何声明一个 hasEq 约束？

How to declare a hasEq constraint?

fstar