Use list monad inside monad transformer type classes?

Question

My goal is to create a function that uses the list monad inside either a ReaderT WriterT stack, or a RWS stack. More generally, how do I use the list monad inside mtl typeclasses such as MonadReader, MonadWriter?

Why am I trying to do this? This problem is an exercise in Beginning Haskell. It asks me to "use functionality from both MonadReader and MonadWriter wrapping the base list monad. To check that the function is general, use two different monads to [test] the requested functionality: ReaderT r (WriterT w []) a and RWST r w s m a" So the book implies this is possible.

I can't figure out how to 'tell' the compiler to use the list monad. If I use ask >>= lift or ask >>= lift . lift I can get either the 2 level stack (RWST []) or 3 level stack (ReaderT WriterT []) to work, but not both.

The focus of my question:

pathImplicitStack' start end | start == end = tell [end]
pathImplicitStack' start end =
  do  (s0, e0) <- ask >>= lift
      guard $ s0 == start
      tell [start]
      pathImplicitStack' e0 end

Additionally, I'd like to know how to type the function. My best attempt so far looks something like pathImplicitStack' :: (MonadReader [(Int, Int)] m, MonadWriter [Int] m, MonadPlus m) => Int -> Int -> m () I know this isn't right, the list monad is probably missing. Also, I think MonadPlus might be useful in the type signature, but I'm not quite sure.

This line: do (s0, e0) <- ask >>= lift is the one giving me trouble. I've tried 0, 1, and 2 lifts without success. I'd like to ask for a [(Int, Int)] and then use the list monad to process just a (Int, Int) (and let the list monad try all possibilities for me).

As part of the exercise, I need to be able to call pathImplicitStack' with both of these functions (or very similar functions):

pathImplicitRW :: [(Int, Int)] -> Int -> Int -> [[Int]]
pathImplicitRW edges start end = execWriterT rdr
  where rdr = runReaderT (pathImplicitStack' start end) edges :: WriterT [Int] [] ()

pathImplicitRWS :: [(Int, Int)] -> Int -> Int -> [[Int]]
pathImplicitRWS edges start end = map snd exec
  where exec = execRWST (pathImplicitStack' start end) edges ()

This is related to my previous question: How do I use list monad inside of ReaderT?

The whole file for easy testing:

{-# LANGUAGE FlexibleContexts #-}

module Foo where

import Control.Monad.Reader
import Control.Monad.Writer
import Control.Monad.RWS

graph1 :: [(Int, Int)]
graph1 = [(2013,501),(2013,1004),(501,2558),(1004,2558)]


pathImplicitRW :: [(Int, Int)] -> Int -> Int -> [[Int]]
pathImplicitRW edges start end = execWriterT rdr
  where rdr = runReaderT (pathImplicitStack' start end) edges :: WriterT [Int] [] ()

pathImplicitRWS :: [(Int, Int)] -> Int -> Int -> [[Int]]
pathImplicitRWS edges start end = map snd exec
  where exec = execRWST (pathImplicitStack' start end) edges ()

pathImplicitStack' :: (MonadReader [(Int, Int)] m, MonadWriter [Int] m, MonadPlus m) => Int -> Int -> [m ()]
pathImplicitStack' start end | start == end = tell [end]
pathImplicitStack' start end =
  do  (s0, e0) <- ask >>= lift
      guard $ s0 == start
      tell [start]
      pathImplicitStack' e0 end

edit

Based on John L's feedback I tried

pathImplicitStack' :: (MonadReader [(Int, Int)] (t []), MonadWriter [Int] (t []), MonadPlus (t []), MonadTrans t) => Int -> Int -> t [] ()
pathImplicitStack' start end | start == end = tell [end]
pathImplicitStack' start end =
  do  (s0, e0) <- ask >>= lift
      guard $ s0 == start
      tell [start]
      pathImplicitStack' e0 end

but as he pointed out, it can only be used with one monad transformer to wrap the list monad, i.e. RSWT, and is not usable with ReaderT WriterT. So this is not the solution I am looking for.

Answer 1

So, the basic problem with doing this within the requirements of the question is that there is no MTL library function for lifting from a list monad that may be arbitrary levels down. However, you can "cheat" a bit: The MonadPlus instance for the combined Monad is inherited from the underlying list monad regardless of the depth, and you can use it to generate the needed action:

  do  (s0, e0) <- ask >>= msum . map return

There is then also an error in the type signature, which needs to be changed to:

pathImplicitStack' :: (MonadReader [(Int, Int)] m, MonadWriter [Int] m, MonadPlus m) => Int -> Int -> m ()

EDIT: Actually on second thought this is not actually cheating. It's just using the MonadPlus API for chaining alternative actions instead of using the underlying list monad directly.