Is there a more readable way to rewrite this pure function to use Writer Monad?

Question

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

However, it was difficult for me to understand the performance of my code on certain inputs. I thought it would be useful to use the Writer monad to put some entries in my code.

It was pretty difficult for me to convert my non-monadic code to monadic. In the end, I got it to compile and run correctly, but the monadic code is much less clear than the original.

The original problem is too complicated to explain here, so I wrote an example with a toy that shows non-monodic and monadic approaches, but actually does not calculate anything useful!

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

import Control.Monad (forM) import Control.Monad.Writer (Writer, runWriter, tell) fun :: Int -> [[Int]] -> [[Int]] fun ab = 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 inconvenient to equip pure Haskell functions that are structured in an algebraic, branched tree, with a monadic function, such as logging, which requires a more “imperative” structure. However, sometimes it’s quite natural to write even pure calculations using monadic combinators, and yours is actually one of them. Namely, the list comprehension that fNonMonadic is based on is mainly used by the list monad; it can be written like this:

 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 with this, it’s much easier to add recording functionality, using it as the basis of the monad transformer stack. Then the list should also be used in the form of a transformer:

 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 ListT documentation warns that the base monad must be commutative, that Writer is not really - the order of the journal entries may be messed up. I do not know if this matters here. If so, check out the alternative implementation suggested by Daniel Wagner .

Answer 2

I looked at several alternatives to Control.Monad.Trans.List and soon installed the ListT module from the Volkov list-t package.

This gives the same result as my ugly fMonadic function, but more readable code. It also works correctly and leads to readable code in a real problem that I want to solve.

In a real task, ListT-based code is a bit slower than ugly code, but the difference is not enough to make a difference.

Thanks again for your help in this matter.

For reference, here is a revised version of a toy example that performs calculations in three different ways and shows that the answer is the same:

 import Control.Monad (forM) import ListT (ListT, fromFoldable, toList) import Control.Monad.Writer (Writer, lift, runWriter, tell) fun :: Int -> [[Int]] -> [[Int]] fun ab = map (map (a +)) b fNonMonadic :: [[Int]] -> [[Int]] fNonMonadic [] = [[]] fNonMonadic (first : rest) = do e <- first s <- fNonMonadic $ fun e rest return $ first ++ s -- The above do notation means the same as this list comprehension: -- [ 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 fMonTrafo :: [[Int]] -> ListT (Writer [String]) [Int] fMonTrafo [] = do lift $ tell ["base case"] return [] fMonTrafo (first : rest) = do e <- fromFoldable first lift $ tell ["recursive case " ++ show e] s <- fMonTrafo $ fun e rest return $ first ++ s main = do let arg = [[0, 1], [20, 30], [400, 500]] let x = fNonMonadic arg print x let (a, b) = runWriter $ fMonadic arg print a mapM_ putStrLn b let (c, d) = runWriter $ toList $ fMonTrafo arg print c mapM_ putStrLn d putStrLn $ if x == a then "fNonMonadic == fMonadic" else error "" putStrLn $ if x == c then "fNonMonadic == fMonTrafo" else error "" putStrLn $ if b == d then "fMonadic log == fMonTrafo log" else error ""