使用达到一定等价性的类型

Question

假设我们想将（有符号的）整数表示为自然数上的 Grothendieck 群（或者，换句话说，表示为一对 (m, n)，其中理解的整数是 m - n） :

data ZTy : Type where
  MkZ : (m, n : Nat) -> ZTy

现在语言免费给我们的（结构）等式已经不是我们想要的了：相反，我们只关心某种等价关系（即(m1, n1) ~ (m2, n2)当且仅当m1 + n2 = m2 + n1） .没什么大不了的，让我们把它写下来！

data Equiv : ZTy -> ZTy -> Type where
  MkEquiv : (prf : m1 + n2  = m2 + n1) -> Equiv (MkZ m1 n1) (MkZ m2 n2)

但是使用它很快就会变得一团糟。 prop Const 类型的任何参数（对于 prop : ZTy -> Type）被替换为 (k : ZTy) -> (k `EqZ` Const) -> prop k，至少可以说（作为一个更实用的例子，我正在努力写下双边归纳证明对于这种类型，我仍然不确定我是否正确地获得了该术语的签名）。

此外，像replaceZ : {P : ZTy -> Type} -> (k1 `Equiv` k2) -> P k1 -> P k2这样的函数（显然）不存在，但我找不到更好的候选者。作为一个有趣的方面 note/observation，如果我们不导出 ZTy 的定义，则没有客户端代码 P 可以观察到它，这函数对任何其他模块中定义的任何 P 都有意义，但看起来我们无法在语言中将其内部化。

我想到的另一件事是将谓词集限制为在等价关系下成立的谓词。也就是说，将 P : ZTy -> Type 替换为 P : ZTy -> Type, pAdmissible : ZPred P 之类的内容，其中 ZPred 会在等价关系下证明其不变性：

data ZPred : Type -> Type where
  MkZPred : {P : ZTy -> Type} ->
            (preservesEquiv : {k1, k2 : ZTy} -> (k1 `Equiv` k2) -> P k1 -> P k2) ->
            ZPred P

无论如何，处理此类类型的常用方法是什么？还有什么可以很好地工作的吗？

我也听说过一些关于商类型的事情，但我了解的不多。

Answer 1

Coq 用 "relation combinators" 的丰富语言描述了这些情况，这是你上一个想法的更好版本。我会翻译它。你有

ZTy : Type -- as yours

然后您继续定义关系和关系上的函数：

-- if r : Relation t and x, y : t, we say x and y are related by r iff r x y is inhabited
Relation : Type -> Type
Relation t = t -> t -> Type

-- if x, y : ZTy, we say x and y are (Equiv)alent iff Equiv x y is inhabited, etc.
Equiv : Relation ZTy  -- as yours
(=)   : Relation a    -- standard
Iso   : Relation Type -- standard

-- f and f' are related by a ==> r if arguments related by a end up related by r
(==>) : Relation a -> Relation b -> Relation (a -> b)
(==>) xr fxr = \f, f' => (x x' : a) -> xr x x' -> fxr (f x) (f' x')
infixr 10 ==>

思路是Equiv、(=)、Iso都是等式关系。 Equiv 和 (=) 是 ZTy 上的两个不同的相等概念，(=) 和 Iso 是 Type 上的两个相等概念。 (==>) 将关系组合成新的关系。

如果你有

P : ZTy -> Type

您想说 Equivalent 参数映射到 Iso 形态类型。也就是说，你需要

replaceP : (x x' : ZTy) -> Equiv x x' -> Iso (P x) (P x')

关系语言有何帮助？好吧，replaceP 本质上是说 P 是 "equal" 自身，在关系 Equiv ==> Iso 下（N.B。Equiv ==> Iso 不是等价的，但它唯一缺少的是反身性。）如果函数在 Equiv ==> Iso 下不是 "equal" 自身，那么它有点像 "contradiction"，而那个函数 "doesn't exist"在你的宇宙中。或者，更确切地说，如果你想写一个函数

f : (ZTy -> Type) -> ?whatever

您可以通过要求像这样的证明参数来限制自己使用正确的函数类型

Proper : Relation a -> a -> Type
Proper r x = r x x

f : (P : ZTy -> Type) -> Proper (Equiv ==> Iso) P -> ?whatever

不过，通常情况下，除非绝对必要，否则您会省略证明。其实标准库中已经包含了很多ZTy上的函数，比如

concatMap : Monoid m => (ZTy -> m) -> List ZTy -> m

不用写 concatMap 证明论证，你真的只需要写一个关于 concatMap 的证明：

concatMapProper : Proper ((Equiv ==> (=)) ==> Pairwise Equiv ==> (=))
-- you'd really abstract over Equiv and (=), but then you need classes for Relations
Pairwise : Relation a -> Relation [a] -- as you may guess

我不知道你想写什么归纳原理，所以我就不管了。但是，您担心

proof : Property Constant

总是需要替换为

proof : (k : ZTy) -> Equiv k Constant -> Property k

只是部分有根据。如果您已经

PropertyProper : Proper (Equiv ==> Iso) Property

你很可能应该这样做，然后你可以写 proper : Property Constant，然后把它推到 PropertyProper 以在需要时概括它。（或者，通过使用顶部带有 PropertyProper 的简单定义，使用通用签名编写 proper）。但是，您无法避免在某处写一个证明，因为它根本不是那么简单。

还值得注意的是 (==>) 除了作为 Proper 的参数之外还有其他用途。它用作通用外延等式：

abs1 : ZTy -> Nat
abs1 (MkZ l r) = go l r
  where go (S n) (S m) = go n m
        go Z     m     = m
        go n     Z     = n
abs2 : ZTy -> Nat
abs2 (MkZ l r) = max l r - min l r

absEq : (Equiv ==> (=)) abs1 abs2
--    : (x x' : ZTy) -> Equiv x x' -> abs1 x = abs2 x'

使用达到一定等价性的类型

Working with types up to a certain equivalence

idris

dependent-type