Is there a more readable way of rewriting this pure function to use the Writer Monad?

Question

I wrote a recursive algorithm using a list comprehension to perform the recursion. I thought my code was clear and easy to read, and the results it produced were correct.

However, I found it difficult to understand the performance of my code on certain inputs. I thought it would be useful to use the Writer monad to put some logging into my code.

I found it quite difficult to convert my non-monadic code to monadic. Eventually I got it to compile and run correctly, but the monadic code is much less understandable than the original.

The original problem is too complex to explain here, so I have written a toy example that shows the non-monadic and monadic approaches, but doesn't actually calculate anything useful!

So my question is: is there a better way to write the function fMonadic, such that it is more readable?

import Control.Monad (forM)
import Control.Monad.Writer (Writer, runWriter, tell)

fun :: Int -> [[Int]] -> [[Int]]
fun a b = map (map (a +)) b

fNonMonadic :: [[Int]] -> [[Int]]
fNonMonadic [] = [[]]
fNonMonadic (first : rest) =
    [ first ++ s
    | e <- first
    , s <- fNonMonadic $ fun e rest]

fMonadic :: [[Int]] -> Writer [String] [[Int]]
fMonadic [] = do
    tell ["base case"]
    return [[]]
fMonadic (first : rest) =
    fmap concat . forM first $ \ e -> do
        tell ["recursive case " ++ show e]
        fmap (map (first ++)) $ fMonadic $ fun e rest

main = do
    let arg = [[0, 1], [20, 30], [400, 500]]
    print $ fNonMonadic arg
    let (a, b) = runWriter $ fMonadic arg
    print a
    mapM_ putStrLn b

Answer 1

It is often awkward to equip pure Haskell functions, which are structured in an algebraic, highly branched tree manner, with a monadic feature such as logging, which requires a more “imperative” structure. However, sometimes it is actually quite natural to write even pure computations using monadic combinators, and yours is in fact one of these. Namely, the list comprehension that's at the heart of fNonMonadic is already basically using the list monad; it can be written thus:

type ListM = []   -- Just to distinguish where I use list as a monad

fNonMonadic :: [[Int]] -> ListM [Int]
fNonMonadic [] = return []
fNonMonadic (first : rest) = do
    e <- first
    s <- fNonMonadic $ fun e rest
    return $ first ++ s

Starting from that, it is much easier to add the writer functionality, by using it as the base of a monad transformer stack. The list must then be used in transformer shape, too:

import Control.Monad.Trans.List

fMonTrafo :: [[Int]] -> ListT (Writer [String]) [Int]
fMonTrafo [] = do
    lift $ tell ["base case"]
    return []
fMonTrafo (first : rest) = do
    e <- ListT $ pure first
    lift $ tell ["recursive case " ++ show e]
    s <- fMonTrafo $ fun e rest
    return $ first ++ s

You may notice that the documentation of ListT warns that the base monad should be commutative, which Writer actually isn't – the order of log entries may get messed up. I don't know if this matters here. If yes, check out the alternative implementation suggested by Daniel Wagner.