2

注意我只是想了解下面显示的这段特定代码中发生了什么。我知道这可能不是解决问题的最佳方法。

我正在尝试使用Writer带有记忆斐波那契函数的惰性单子来计算函数被调用的次数。该函数快速返回正确的值，但Writer环境永远不会返回并且不使用任何 CPU 或内存。

import Control.Monad.Writer.Lazy as W

fib :: Int -> Writer (Sum Int) Int
fib = let fibs = mapM fib' [0..]
          fib' 0 = return 0
          fib' 1 = return 1
          fib' n = liftM2 (+) (fib $ n-1) (fib $ n-2)
      in \n -> tell (Sum 1) >> fibs >>= return . (!!n)

Prelude W> runWriter $ fib 51
(20365011074,Sum {getSum = Interrupted.

有人可以解释发生了什么吗？为什么环境不返回值？

编辑

无限列表[0..]不是这里的问题。我尝试用有限的列表替换它，例如[0..10]or[0..n]但问题仍然存在。 如果无限列表是问题所在，那将是一个非常占用内存的计算，这就是为什么我在上面提到它不消耗任何 CPU 或内存，这让我感到困惑。

fib我相信，由于懒惰，在评估函数的节点时会以某种方式发生死锁。

4

1 回答 1

3

问题是mapM fib' [0..]。这是计算 monad 中的无限列表的有效计算，在这种情况下，它还需要组合无限数量的效果tell (Sum 1)。由于Writer的懒惰，您可以访问结果，但幺半群部分内的计数永远不会完成。

更新：即使您使列表有限，它仍然无法正常工作。问题在于它mapM fib' [0..10]表示“斐波那契数列和计算它们所需的调用总数”。因此，在您的表达式中tell (Sum1) >> fibs >>= ...，您总是将所有调用的总数添加到计数器，这显然是您不想要的。

此外，它会创建一个无限循环：对 invokes 的任何fib调用fib'，它都会计算对其所有元素的调用次数，因此调用（在其他调用中）fib' 2，它会fib再次调用。仅当您将列表限制为 时，无限递归才会停止[0..1]。同样，问题在于mapM结合了给定一元计算的所有效果。

相反，你需要这样的东西：

import Control.Monad.Writer.Lazy as W

fib :: Int -> Writer (Sum Int) Int
fib = let fibs = map fib' [0..] -- <<<<
          fib' 0 = return 0
          fib' 1 = return 1
          fib' n = liftM2 (+) (fib $ n-1) (fib $ n-2)
      in \n -> tell (Sum 1) >> fibs !! n -- <<<<

在这里fibs :: [Writer (Sum Int) Int]，因此对于每个元素，它都包含结果和计算所需的调用次数。

于 2014-03-02T16:59:19.377 回答