The problem is mapM fib' [0..]
. This is an effectful computation that computes an infinite list within the monad, and for it it also needs to combine an infinite number of effects, in this case tell (Sum 1)
. Thanks to Writer
's lazyiness, you can access the result, but the count inside the monoid part never finishes.
Update: Even if you make the list finite, it still won't work. The problem is that mapM fib' [0..10]
represents "the list of Fibonacci numbers and the total number of calls needed to compute them". So in your expression tell (Sum1) >> fibs >>= ...
you always add the total number of all calls to the counter, which is clearly something you don't want.
Moreover, it creates an infinite loop: Any call to fib
invokes fib'
, which computes the number of calls for all its elements, hence invoking (among other calls) fib' 2
, which calls fib
again. The infinite recursion stops only if you limit the list to [0..1]
. Again, the problem is that mapM
combines all the effects of given monadic computations.
Instead, you need something like this:
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 -- <<<<
Here fibs :: [Writer (Sum Int) Int]
, so for each element it contains both the result and the number of calls needed for its computation.