什么构成了编程环境中的余数据？

Question

这是一个 corecursive 算法，因为每次迭代它都会根据比之前更大的数据调用自身：

iterate f x =  x : iterate f (f x)

它类似于尾递归累加器样式，但它的累加器是隐式的，而不是作为参数传递。如果不是因为懒惰，它将是无限的。那么 codata 只是 WHNF 中值构造函数的结果，有点像 (a, thunk) 吗？或者 codata 是范畴论中的数学术语，在编程领域没有有用的表示？

追问：value recursion只是corecursion的同义词吗？

Answer 1

我认为回答你的问题需要很多的解释，所以这里有一个很长的答案，最后对你的问题有具体的回答。

Data 和 codata 在范畴论方面有正式的数学定义，所以 而不是 只是它们在程序中的使用方式的问题（即，不仅仅是 "application context" 你在评论中提到）。在 Haskell 中可能看起来是这样，因为语言的特性（特别是非终止和惰性）最终模糊了区别，所以 在 Haskell 中，所有数据也是codata，反之亦然，但不一定是这样，有些语言可以更清楚地区分。

data 和 codata do 在编程领域都有有用的表示，这些表示与递归和核心递归产生了自然关系。

如果不快速掌握技术知识，很难解释这些正式的定义和表示，但粗略地说，数据类型，例如，整数列表，是一种类型L 连同构造函数：

makeL :: Either () (Int, L) -> L

这在某种程度上 "universal" 因为它可以完全代表任何此类结构。（在这里，您想将 LHS 类型 Either () (Int, L) 解释为表示列表 L 是空列表 Left () 或由头元素 h :: Int 和尾列表 t :: L.)

从一个反例开始，L = Bool 不是我们正在寻找的数据类型，因为即使你可以写：

foo :: Either () (Int, Bool) -> Bool
foo (Left ()) = False
foo (Right (h, t)) = True

到"construct"一个Bool，这不能完全代表任何这样的构造。比如两个构造：

foo (Right (1, foo (Left ()))) = True
foo (Right (2, foo (Left ()))) = True

给出相同的Bool值，尽管他们使用了不同的整数，所以这个Bool值不足以完全表示构造。

相比之下，类型 [Int] 是合适的数据类型，因为（几乎微不足道的）构造函数：

makeL :: Either () (Int, [Int]) -> [Int]
makeL (Left ()) = []
makeL (Right (h, t)) = h : t

完全代表任何可能的结构，为每一个创造一个独特的价值。所以，它在某种程度上是类型签名 Either () (Int, L) -> L.

的 "natural" 构造

类似地，整数列表的 codata 类型 将是一个类型 L 和一个析构函数：

eatL :: L -> Either () (Int, L)

从某种意义上说，它可以代表任何可能的破坏"universal"。

同样，从一个反例开始，一对 (Int, Int) 不是我们正在寻找的余数据类型。例如，对于析构函数：

eatL :: (Int, Int) -> Either () (Int, (Int, Int))
eatL (a, b) = Right (a, (b, a))

我们可以代表破坏：

let p0 = (1, 2)
    Right (1, p1) = eatL p0
    Right (2, p2) = eatL p1
    Right (1, p3) = eatL p2
    Right (2, p4) = eatL p3
...continue indefinitely or stop whenever you want...

但我们不能代表破坏：

let p0 = (?, ?)
    Right (1, p1) = eatL p0
    Right (2, p2) = eatL p1
    Right (3, p3) = eatL p2
    Left () = eatL p3

另一方面，在 Haskell 中，列表类型 [Int] 是整数列表的适当余数据类型，因为析构函数：

eatL :: [Int] -> Either () (Int, [Int])
eatL (x:xs) = Right (x, xs)
eatL [] = Left ()

可以表示任何可能的破坏（包括有限或无限破坏，感谢 Haskell 的惰性列表）。

（作为证明这并非全是挥手的证据，如果您想将其与形式数学联系起来，在技术范畴论术语中，以上内容相当于说类似列表的内函子：

F(A) = 1 + Int*A   -- RHS equivalent to "Either () (Int,A)"

产生了一个类别，其对象是构造函数（也称为 F 代数）1 + Int*A -> A。与 F 关联的 data 类型是此类中的初始 F 代数。 F 还产生了另一个类别，其对象是析构函数（又名 F-coalgebras）A -> 1 + Int*A。与 F 关联的 codata 类型是该类别中的最终 F-余数。）

按照@DanielWagner 的建议，用直观的术语来说，数据类型是表示类列表对象的任何构造的一种方式，而余数据类型是表示类列表对象的任何破坏的一种方式。在 data 和 codata 不同的语言中，存在一个基本的不对称性——终止程序只能构造一个有限列表，但它可以破坏一个无限列表（的第一部分），因此 data 必须是有限的，但 codata 可以是有限的或无限。

这导致了另一个并发症。在 Haskell 中，我们可以使用 makeL 构造一个无限列表，如下所示：

myInfiniteList = let t = makeL (Right (1, t)) in t

请注意，如果 Haskell 不允许对非终止程序进行惰性评估，这将是不可能的。因为我们可以做到这一点，根据 "data" 的正式定义，Haskell 整数列表数据类型 还必须包括无限列表 ！即Haskell"data"可以无限大

这可能与您在其他地方阅读的内容相冲突（甚至与@DanielWagner 提供的直觉相冲突），其中 "data" 仅用于指代有限数据结构。好吧，因为 Haskell 有点奇怪，而且因为在数据和余数据不同的其他语言中不允许无限数据，当人们谈论 "data" 和 "codata" 时（即使在 Haskell) 并且有兴趣进行区分，他们可以使用 "data" 仅指代有限结构。

递归和核心递归适合这种情况的方式是，普遍性属性自然地让我们 "recursion" 消费数据，"corecursion" 产生余数据。如果 L 是具有构造函数的整数列表数据类型：

makeL :: Either () (Int, L) -> L

那么使用列表 L 生成 Result 的一种方法是定义一个（非递归）函数：

makeResult :: Either () (Int, Result) -> Result

此处，makeResult (Left ()) 给出空列表的预期结果，而 makeResult (Right (h, t_result)) 给出头部元素为 h :: Int 且尾部元素将给出结果的列表的预期结果t_result :: Result.

根据普适性（即 makeL 是初始 F 代数的事实），存在唯一函数 process :: L -> Result "implements" makeResult。实践中会递归实现：

process :: [Int] -> Result
process [] = makeResult (Left ())
process (h:t) = makeResult (Right (h, process t))

相反，如果 L 是具有析构函数的整数列表余数据类型：

eatL :: L -> Either () (Int, L)

然后从 Seed 生成列表 L 的一种方法是定义一个（非递归）函数：

unfoldSeed :: Seed -> Either () (Int, Seed)

此处，unfoldSeed 应为每个所需的整数生成一个 Right (x, nextSeed)，并生成 Left () 以终止列表。

根据普遍性（即 eatL 是最终 F-coalebra 的事实），存在一个独特的函数 generate :: Seed -> L 即 "implements" unfoldSeed。在实践中，它会被核心递归地实现：

generate :: Seed -> [Int]
generate s = case unfoldSeed s of
  Left () -> []
  Right (x, s') -> x : generate s'

综上所述，这里是您最初问题的答案：

从技术上讲，iterate f 是核心递归的，因为它是唯一的余数据生成函数 Int -> [Int]，它实现了：
```
unfoldSeed :: Seed -> Either () (Int, Seed)
unfoldSeed x = Right (x, f x)
```
通过上面定义的generate。
在Haskell中，生成类型[a]的codata的corecursion依赖于惰性。然而，严格的余数据表示是可能的。例如，以下余数据表示在 Strict Haskell 中运行良好，可以安全地进行全面评估。
```
data CoList = End | CoList Int (() -> CoList)
```
下面的 corecursive 函数产生了一个 CoList 值（我把它设为有限只是为了好玩——它也很容易产生无限的 codata 值）：
```
countDown :: Int -> CoList
countDown n | n > 0 = CoList n (\() -> countDown (n-1))
            | otherwise = End
```
所以，不，codata 不仅仅是 WHNF 中具有 (a, thunk) 或类似形式的值的结果，而且 corecursion 不是值递归的同义词。但是，WHNF 和 thunk 提供了一种可能的实现，并且是 "standard" Haskell 列表数据类型也是 codata 类型的实现级原因。

什么构成了编程环境中的余数据？

What constitutes codata in the context of programming?

recursion

haskell

functional-programming

codata

corecursion