9

所以今晚我在想一个图距离算法，在我开车的时候想出了这个：

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.

但现在我想我已经想通了。

在处理核心递归数据时，是否有一份我可以阅读的常见错误和反模式列表，以便我可以训练我的大脑进行核心递归思考？经验已经很好地训练了我思考非核心数据的能力，但如果可以的话，我想从其他人的错误中学习。

4

1 回答 1

13

好吧，在处理核心递归数据时确实只有一个基本错误，那就是粗心地使用递归！

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]：实际上，它会在某些输入上失败（例如，一些断开的图），但这是一个不同的问题。

于 2011-06-08T04:05:25.387 回答