类型级固定点，同时确保终止

Question

可以向某些人表示如何使 unFix 总计？可能通过限制 f 是什么？

record Fix (f : Type -> Type) where
    constructor MkFix
    unFix : f (Fix f)

> :total unFix
Fix.unFix is possibly not total due to:
    MkFix, which is not strictly positive

Answer 1

这里的问题是 Idris 无法知道您为数据类型使用的基本仿函数是否严格为正。如果它接受你的定义，你就可以将它与具体的负函子一起使用，并从中证明 Void。

有两种表示严格正函子的方法：定义一个宇宙或使用容器。我已经把所有的东西都放在 two self-contained gists 里了（但是那里没有评论）。

严格正函子的宇宙

您可以从基本表示开始：我们可以将函子分解为 sigma 类型 (Sig)、递归子结构的（严格正向）位置 (Rec) 或什么都没有（End）。这给了我们这个描述及其作为 Type -> Type 函数的解码：

-- A universe of positive functor
data Desc : Type where
  Sig : (a : Type) -> (a -> Desc) -> Desc
  Rec : Desc -> Desc
  End : Desc


-- The decoding function
desc : Desc -> Type -> Type
desc (Sig a d) x = (v : a ** desc (d v) x)
desc (Rec d)   x = (x, desc d x)
desc End       x = ()

一旦你有了这个保证严格为正的函子域，你就可以取它们的最小不动点：

-- The least fixpoint of such a positive functor
data Mu : Desc -> Type where
  In : desc d (Mu d) -> Mu d

您现在可以定义自己喜欢的数据类型。

示例：自然

我们从每个构造函数的总和类型标签开始。

data NatC = ZERO | SUCC

然后，我们通过将构造函数标记存储在 sigma 中并根据标记值计算其余描述来定义严格正基函子。 ZERO 标签与 End 关联（zero 构造函数中没有其他内容可存储），而 SUCC 标签需要 Rec End，即说一个对应于 Nat 的前身的递归子结构。

natD : Desc
natD = Sig NatC $ \ c => case c of
  ZERO => End
  SUCC => Rec End

然后我们的归纳类型通过取描述的不动点得到：

nat : Type
nat = Mu natD

我们自然可以恢复我们期望的构造函数：

zero : nat
zero = In (ZERO ** ())

succ : nat -> nat
succ n = In (SUCC ** (n, ()))

参考资料

这个特定的宇宙取自 McBride 的 'Ornamental Algebras, Algebraic Ornaments'，但您可以在 Chapman、Dagand、McBride 和 Morris 的 'The Gentle Art of Levitation' 中找到更多详细信息。

作为容器扩展的严格正函子

第二种表示是基于另一种分解：每个归纳类型被看作是一个通用的形状（即它的构造函数和它们存储的数据）加上一些递归位置（这可以取决于形状的具体值).

record Container where
  constructor MkContainer
  shape : Type
  position : shape -> Type

我们可以再次将其解释为 Type -> Type 函数：

container : Container -> Type -> Type
container (MkContainer s p) x = (v : s ** p v -> x)

并取如此定义的严格正函子的不动点：

data W : Container -> Type where
  In : container c (W c) -> W c

您可以通过定义 Container 感兴趣的数据类型再次恢复您最喜欢的数据类型。

示例：自然

自然数有两个构造函数，每个构造函数都不存储任何内容。所以形状将是 Bool。如果我们在 zero 的情况下，则没有递归位置 (Void)，而在 succ 的情况下，只有一个 (()).

natC : Container
natC = MkContainer Bool (\ b => if b then Void else ())

我们的类型是通过容器的固定点得到的：

nat : Type
nat = W natC

并且我们可以恢复通常的构造函数：

zero : nat
zero = In (True ** \ v => absurd v)

succ : nat -> nat
succ n = In (False ** \ _ => n)

参考资料

这是基于 Abbott、Altenkirch 和 Ghani 的 'Containers: Constructing Strictly Positive Types'。

类型级固定点，同时确保终止

Type Level Fix Point while Ensuring Termination

idris

严格正函子的宇宙

示例：自然

参考资料

作为容器扩展的严格正函子

示例：自然

参考资料