2

有人能告诉我为什么这段使用 State monad 的代码永远不会结束吗？

fib' :: State [Int] ()
fib' = do l <- get
          let l2 = sum (last2 l)
          put (l ++ [l2])
          return ()
          fib'

take 10 $ execState fib' [0, 1]

当我在 ghci REPL 中执行它时，该函数执行时不会停止。

4

5 回答 5

8

的结果execState是计算结束时的状态值。但是你的计算永远不会结束：fib'调用fib'. 虽然在您的情况下可以证明状态的前 10 个元素最终不会改变，但编译器无法预测（也不应该）。

您可能想查看 Writer Monad，您可以在其中懒惰地处理写入的数据。

于 2013-08-12T10:39:22.387 回答
4

return不像在命令式语言中那样工作。对于每个 monad，它的定义不同，对于 state monad，它被定义为： return x = State $ \s -> (x,s)

所以它实际上并没有脱离fib'函数，而是将一个新的 State monad 绑定到计算的其余部分。

编辑：

虽然我最初的答案是正确的，但它并没有回答 OP 的问题。在 OP 的代码中，return充当无操作。对于 OP 的代码永远不会终止的原因，请参阅其他答案。我仍然在这里留下我的答案，因为我觉得指出它仍然很重要，因为它return确实不必要地出现在 OP 的代码示例中

于 2013-08-12T10:40:17.437 回答
4
  1. return ()线是多余的，可以删除
  2. (++)几乎总是一个坏主意，因为它的第一个参数的大小是 O(N)。
  3. 您构建了许多长度增加的列表，而您的目标是构建一个无限列表
于 2013-08-12T10:51:49.937 回答
1

您在这里所做的或多或少等同于以下内容：

rfib (last:last':rest) = let new = last + last' in rfib (new:last:last':rest)

它试图“懒惰”地以相反的顺序创建数字。（顺序并不重要，我只是反过来做以摆脱分散注意力的（++）和last2）。

但关键是，你永远不会计算一个列表，因为类型检查器会告诉你。例如，以下都是很好的类型：

res1 = (take 10 . rfib) [1,0] :: [Int]   
res2 = (take 10 . snd . rfib) [1,0] :: [Int]   
res3 = (take 10 . snd . snd . rfib) [1,0] :: [Int]   
res4 = "foo" == rfib [1,0]

你知道，有时不写注释是个好主意。然后你会看到类似这样的推断：

rfib :: Num a => [a] -> b

这与您的 foo' 的主要类型密切相关：

fib' :: Num a => State [a] b

这种类型的你应该考虑一下。它的情况rfib告诉你，你不知从哪里创建了一个你想要的任何类型的值，这里称为b. 这就是“没有这样的价值”的同义词。与head []orunJust Nothing或一样error "Bottom"，任何计算该值的尝试都必须发散。

当结果中出现的新类型变量被类型构造函数“保护”时，情况就不同了。然后会发生什么将取决于类型，其构造函数被应用。就目前而言，它适用于 Writer，但不适用于 State。尽管如此，这种出乎意料的类型应该让人们重新考虑一下。

于 2013-08-12T15:35:08.373 回答
1

在@Joachim Breitner 的建议下，使用惰性 Writer monad 的可能解决方案是：

import Control.Monad.Writer

fib' :: Writer [Int] ()
fib' = tell [1, 1] >> go 1 1
    where
        go :: Int -> Int -> Writer [Int] ()
        go f1 f2 = do
            let f3 = f1 + f2
            tell [f3]
            go f2 f3

main = print $ take 10 $ execWriter fib'
于 2013-08-12T13:27:50.100 回答