Haskell:常见的核心递归谬误

Question

所以今晚我正在考虑图距离算法，并想出了这个当我开车时:

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.

但现在我想我已经想清楚了。

是否有常见错误和反模式的列表当处理我可以阅读的核心数据时，这样我就可以训练我的大脑进行核心递归思考？经验很好地训练了我通过非核心递归进行思考数据，但如果可以的话，我想从其他人的错误中吸取教训。

Answer 1

嗯，处理核心递归数据时实际上只有一个根本性错误，那就是不小心使用了递归!

Corecursion 意味着数据在某种意义上是增量生成的。您的图形距离函数在这里很有启发性，因为它似乎应该起作用，因此请考虑增量部分应该在哪里:起点是从节点到自身的距离 0，否则大于 1比它自己的近邻之间的最小距离。因此，我们期望每个距离值都是增量的，这意味着我们需要它们本身具有适当的核心递归性。

所讨论的递归是由于 (+) 和 minimum 的组合而发生的:当找到最小值时，1总是小于 1 + n，而不需要担心 n 是什么...但是没有办法比较 Int 而没有计算整个值。

简而言之，该算法期望能够仅根据需要比较 (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 算法的驱动下增量消耗；数据可以递归生成，受递归算法限制。

你不能做的是递归地使用codata(例如，向左折叠无限列表)或以递归方式生成核心数据(由于懒惰，在Haskell中很少见)。

[0]:实际上，它在某些输入上会失败(例如，一些断开连接的图表)，但这是一个不同的问题。