How to properly combine List[M[List[A]]] into M[List[A]] if M is a monad?

Question

I have monads that wrap lists. I would like to combine these monads to form a monad that wraps the concatenation of all the lists.

M[List[A]] + M[List[A]] ==> M[List[A]]

To achieve this I did the following (pseudo-code):

(1 to 10).foldLeft(Option(List(0)))((accumulator, i) => {
  for {
    prev <- accumulator
    more <- Option(List(i))
  } yield prev ++ more
})

This seems to compile but I kinda feel it should be simpler and shorter than this. Any ideas for improvement?

Answer 1

There is an instance of Traverse[List]. Every Monad[M] is a special case of Applicative[M]. Therefore, if you have a

List[M[List[A]]]

you should be able to use sequence in Traverse[List] with the Applicative[M] to first transform it into

M[List[List[A]]]

and then use map from Functor[M] to flatten it into

M[List[A]]

Something like

val lists: List[Option[List[A]]] = ???
val optLists: Option[List[List[A]]] = Traverse[List].sequence(lists)
val optList: Option[List[A]] = optLists.map(_.flatten)

in the case of Option.