There is bug in calculating Fibonacci numbers - Haskell

Question

I solve different problems in some judging systems. Today I want to calculate Fibonacci numbers with State Monad. My code works well and it pass all my tests. But there is some error (one test is failed), which I can not determine.

My code is:

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

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

Can you help me to find the error? I don't know, where error is.

Answer 1

I think your code IS correct, tested using a naive implementation fib0 from here

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)

I tried:

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

and got

[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]

Your function seems to give identical results as expected ones.