好吧,在处理核心递归数据时确实只有一个基本错误,那就是粗心地使用递归!
Corecursion 意味着数据在某种意义上是增量生成的。您的图形距离函数在这里很有指导意义,因为它似乎应该起作用,所以请考虑增量部分应该在哪里:起点是节点到自身的距离为 0,否则大于其自身之间的最小距离直接邻居。因此,我们希望每个距离值都是递增的,这意味着我们需要它们本身具有适当的核心递归性。
那么,有问题的递归是由于 和 的组合而发生的(+)
:minimum
当找到最小值时,1
将始终小于1 + n
,而无需担心是什么n
……但是如果Int
不计算整个值,就无法比较 s 。
简而言之,该算法希望能够仅根据需要比较(1 +)
应用了多少次;0
也就是说,它想要使用“零”和“继任者”定义的惰性自然数。
看哪:
data Nat = Z | S Nat
natToInt :: Nat -> Int
natToInt Z = 0
natToInt (S n) = 1 + natToInt n
instance Show Nat where show = show . natToInt
instance Eq Nat where
Z == Z = True
(S n1) == (S n2) = n1 == n2
_ == _ = False
Z /= Z = False
(S n1) /= (S n2) = n1 /= n2
_ /= _ = True
instance Ord Nat where
compare Z Z = EQ
compare Z (S _) = LT
compare (S _) Z = GT
compare (S n1) (S n2) = compare n1 n2
然后在 GHCi 中:
> distance 1 $ fromList [(0,[1]),(1,[0,2]),(2,[1,3]),(3,[2])]
fromList [(0,1),(1,0),(2,1),(3,2)]
证明您的算法有效[0];你的实现是不正确的。
现在,作为一个细微的变化,让我们将您的算法应用于不同的图表:
> distance 1 $ fromList [(0,[1]),(1,[0]),(2,[3]),(3,[2])]
...我们期望这会做什么?节点 2 或 3 到节点 1 的距离是多少?
在 GHCi 中运行它有明显的结果:
fromList [(0,1),(1,0),(2,^CInterrupted.
然而,该算法在该图上正常工作。你能看出问题吗?为什么它挂在 GHCi 中?
综上所述,需要明确区分两种不能自由混合的形式:
- 懒惰的,可能是无限的数据,以核心递归方式生成
- 有限数据,递归消费
两种形式都可以以与结构无关的方式进行转换(例如,map
都适用于有限和无限列表)。Codata 可以增量使用,由核心递归算法驱动;数据可以递归生成,受递归算法的限制。
你不能做的是递归地使用 codata(例如,左折叠一个无限列表)或核心递归地生成数据(在 Haskell 中很少见,由于懒惰)。
[0]:实际上,它会在某些输入上失败(例如,一些断开的图),但这是一个不同的问题。