haskell - 为什么代数类型只是初始代数(反之亦然)？

Question

在 recursion-schemes包我们可以表达一个(严格正数)代数数据类型的事实

有一个签名仿函数，f

是初始 f -代数和

是最后的f -代数

例如，我们可以为 [a] 这样做。使用以下代码

-- (1) define and declare the signature functor, here called Base

data instance Prim [a] x = Nil | Cons a x deriving Functor
type instance Base [a] = Prim [a]

-- (2) demonstrate the initial algebra
instance Foldable [a] where
  project []     = Nil
  project (a:as) = Cons a as

-- (3) demonstrate the final coalgebra
instance Unfoldable [a] where
  embed Nil         = []
  embed (Cons a as) = a:as

值得注意的是，对于我们有 (1)、(2) 和 (3) 的任何类型，我们应该有 (project, embed)见证同构。

我的理解是，一般的数据类型(或至少是严格正数的)总是一些签名仿函数的最终/初始 co/代数——事实上，它们总是两者兼而有之。

所以我的问题是:为什么有 Foldable和 Unfoldable作为单独的类(class)？什么时候数据类型只是其中一种？

目前我可以想象这对于只想提供折叠或展开接口(interface)的抽象数据类型可能很有值(value)，但还有其他时间吗？

Answer 1

这可能不是您问题的答案，但严格肯定的 Haskell 数据类型是初始代数并不是真的。这样做的原因是，即使在 Haskell 的全部子集中(这是我们在推理时想要处理的内容!)你也有无限的数据。

例如，无限列表的折叠是部分的。