所以我今晚在考虑一种图形距离算法，并提出了
当我开车时:
module GraphDistance where
import Data.Map
distance :: (Ord a) => a -> Map a [a] -> Map a Int
distance a m = m'
where m' = mapWithKey d m
d a' as = if a == a' then 0 else 1 + minimum (Prelude.map (m'!) as)
起初，我很为自己感到骄傲，因为它看起来如此优雅。
但是后来我意识到这行不通-corecursion可能会卡住
在一个循环中。
我不得不编写代码以说服自己:
ghci> distance 1 $ fromList [(0,[1]),(1,[0,2]),(2,[1,3]),(3,[2])]
fromList [(0,1),(1,0),(2,^CInterrupted.
但是现在我想我已经考虑了很多。
是否有常见错误和反模式的列表
在处理我可以继续阅读的corecursive数据时，
这样我就可以训练我的大脑进行核心的思考？经验
通过非corecursive思考对我有很好的训练
数据，但如果可以的话，我想向别人学习错误。
最佳答案
好吧，在处理核心递归数据时，实际上仅存在一个基本错误，并且粗心地在其上使用了递归!
Corecursion意味着从某种意义上说，数据是增量生成的。您的图距离函数在这里很有启发性，因为它似乎应该起作用，因此请考虑增量部分应位于的位置:起点是节点到其自身的距离为0，否则大于其自身之间的最小距离。直系邻居。因此，我们希望每个距离值都是递增的，这意味着我们需要自己适本地进行核心递归。
然后，由于(+)和minimum的组合而发生了递归问题:找到最小值时，1始终小于1 + n，而不必担心n是什么...但是无法比较Int s而不计算整个值(value)。
简而言之，该算法希望能够仅根据需要比较(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可以在corecursive算法的驱动下逐步使用。数据可以递归生成，受递归算法限制。您无法做的是递归使用协数据(例如，左折叠无限列表)或以核心方式递归生成数据(由于懒惰而在Haskell中很少见)。
[0] :实际上，它在某些输入(例如，某些断开的图形)上将失败，但这是另一个问题。