Memoization in the Writer monad

Question

NOTE I'm just trying to understand what's happening in this particular piece of code shown below. I know this might not be the best way to solve the problem.

I'm trying to use the lazy Writer monad with a memozied fibonacci function to count the number of times the function is called. The function returns the correct value fast but the Writer environment never returns and doesn't use any CPU or memory.

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.

Can someone explain what's going on? Why doesn't the environment return a value?

EDIT

The infinite list [0..] is not the problem here. I've tried replacing it by a limited list such as [0..10] or [0..n] but the problem still persists. If the infinite list was the problem it would've been a very memory-intensive computation and that's why I mentioned above that it doesn't consume any CPU or memory which is what confuses me.

I believe that, due to laziness, there's a deadlock occurring somewhere somehow when evaluating the nodes of the fib function.

Your guess is correct. Every call to fib tries to execute the monadic action fibs, which eventually tries to evaluate itself so it gets stuck. And because this is done using graph reduction, no actual computation is taking place just a node is being blocked on itself. Due to purity the compiler doesn't need to keep traversing this infinite cycle in the graph, so it doesn't, which explains the cpu/memory usage thing. — is7s

Petr Petr · Accepted Answer · 2014-03-02T16:59:19

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.

Memoization in the Writer monad

1 Answers