How do I use list monad inside of ReaderT?

Question

How do I use Reader/ReaderT to ask for a list type, e.g. [(Int, Int)] and then perform calculations inside the list monad (of the type that was asked for)?

My broken code follows, shortened for clarity:

attempt :: Int -> Int -> ReaderT [(Int,Int)] [] [[Int]]
attempt start end =
  do  (s0, e0) <- ask
      return [0]

To give you an idea of what I'm trying to do, here is the same function, using the list monad but not Reader:

paths :: [(Int, Int)] -> Int -> Int -> [[Int]]
paths edges start end =
  if start == end
    then return [end]
    else do   (s0, e0) <- edges
              guard $ s0 == start
              subpath <- paths edges e0 end
              return $ s0 : subpath

I'm using ReaderT because I'm learning monad transformers. It's part of a larger problem using both Reader and Writer and list monad to implement paths.

Answer 1

The trick here is to use lift to convert a list monad (ie an [a]) into a ReaderT env [] by using lift:

lift :: (Monad m, MonadTrans t) => m a -> t m a

or specialized to your monad stack:

lift :: [a] -> ReaderT [(Int,Int)] [] a

ask returns the state (ie [(Int, Int)]) wrapped in the ReaderT monad eg:

ask :: ReaderT [(Int, Int)] [] [(Int, Int)]

We want to convert that into another value in the same monad but with the type:

??? :: ReaderT [(Int, Int)] [] (Int, Int)

So the alternatives are tracked by the monad instead of in the output. Consider the basic function >>=:

(>>=) :: Monad m => m a -> (a -> m b) -> m b

You should be able to see we have all the pieces required. Using ask >>= lift:

1. The first argument is ReaderT [(Int, Int)] [] [(Int, Int)], meaning a is [(Int, Int)], and m is ReaderT [(Int, Int)] []
2. We want the result m b to be ReaderT [(Int, Int)] [] (Int, Int), so b is (Int, Int)
3. So the function needs the type [(Int, Int)] -> ReaderT [(Int, Int)] [] (Int, Int). If you replace the a in the lift function with (Int, Int), it is a perfect match, meaning the expression ask >>= lift does what you want.

The other mistake you had was the output type of the ReaderT monad - as it contained a list monad you didn't need to wrap the result in another pair of brackets. A ReaderT state [] already contains the concept of multiple results, and a single result in this case is a [Int] showing the graph path.

Here is the working code:

{-# LANGUAGE GeneralizedNewtypeDeriving #-}
{-# LANGUAGE MultiParamTypeClasses #-}
module Main where
import Control.Monad.Reader
import Control.Applicative


paths :: Int -> Int -> ReaderT [(Int,Int)] [] [Int]
paths start end = do
  if start == end
     then return [end]
     else do
      (s0, e0) <- ask >>= lift
      guard $ s0 == start
      (s0 :) <$> paths e0 end


input :: [(Int, Int)]
input = [(1,2), (2,7), (3,4), (7, 3), (7, 5), (5, 3)]

test :: [[Int]]
test = runReaderT (paths 2 4) input


> test
[[2,7,3,4],[2,7,5,3,4]]

I hope that explains it clearly. In this situation, I would probably just stick with the original solution (using Reader by itself is normally not very useful), but it is good to know how to understand and manipulate the types of monads and monad transformers.