计算斐波那契数时存在错误 - Haskell

Question

我在一些判断系统中解决了不同的问题。今天我想用 State Monad 计算斐波那契数列。我的代码运行良好并且通过了我所有的测试。但是有一些错误（一个测试失败），我无法确定。

我的代码是：

fib :: Int -> Integer
fib n = fst $ execState (replicateM n fibStep) (0,1)

fibStep :: State (Integer,Integer) ()
fibStep = do modify (\(a, b) -> (b, a + b))

你能帮我找出错误吗？不知道哪里出错了

Answer 1

我认为您的代码是正确的，使用来自 here

的天真的实现 fib0 进行了测试

import Control.Monad.State

fib :: Int -> Integer
fib n = fst $ execState (replicateM n fibStep) (0,1)

fibStep :: State (Integer,Integer) ()
fibStep = do modify (\(a, b) -> (b, a + b))

fib0 0 = 0
fib0 1 = 1
fib0 n = fib0 (n-1) + fib0 (n-2)

我试过了：

*Main> map (\x -> fib x - fib0 x) [1..25]

得到了

[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]

您的函数似乎给出了与预期相同的结果。