最小的固定点,最大的固定点



在像Haskell这样的懒惰的非完全语言中,最小的固定点和最大的固定点是如何重合的。完全偏序的连续性与此有什么关系?

在CPO(我们将类型解释为(中,任何递增链都具有最小上界。

这里有一个例子,应该传达为什么在CPO领域,最小不动点和最大不动点重合的直觉。考虑以下函子,为了简洁起见滥用列表表示法:

data ListF a x = [] | a : x

它最大的不动点是Haskell列表的类型(可能是无限的,也可能是部分的(。它的最小不动点呢?以下元素必须在其中(省略了Fix构造函数(:

0 : _|_
0 : 1 : _|_
0 : 1 : 2 : _|_
...

它们形成了一个递增链,所以必须有一个最小上界,它必须是自然整数0 : 1 : 2 : ...的无限列表。因此,ListF的最小不动点包含无限个列表,因此与最大不动点重合。


正如评论中所指出的,最大不动点由类型[]给出的说法可能需要澄清。例如,一些由大型序数索引的列表的CPO"BigList"难道不会成为更大的固定点吗?

首先可以证明[]满足最终ListF-余代数的定义。然后,最终余代数的一个性质是它们在同构之前是唯一的。因此,由较大序数索引的列表将导致非同构CPO,因此这不可能是最终的余数。

我可以到此为止,但请稍等,BigList不是还是ListF的一个更大的固定点吗?我的结论是,把这个问题归结为糟糕的术语,从形式上讲,我们应该只讨论"最终的联合体",而不是"最大的固定点"。

根据你如何定义CPO中函子的"不动点"和CPO之间的(预(序概念,你可能会发现BigListListF的不动点,它大于[],当你到达"最大不动点"时,你会遇到集合论悖论,最终,对于Haskell从业者来说,将"最大不动点"形式化并没有什么价值,因为你实际上想要一个最终的coalgebra的良好性质。

(我很想知道一种直接的方法来定义"不动点",将BigList排除在外。(

因此,"最大不动点"一词可能是"最终余数"的同义词。有些直觉会延续("不动点"通常可以通过迭代来接近(,有些则不会(它不是集合论意义上的"最大"(。

相关内容

  • 没有找到相关文章

最新更新