# Memoization in the Writer monad

•  19-10-2022
•  |
•

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.

Solution

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.