Как правильно объединить List [M [List [A]]] в M [List [A]], если M является монадой?

Question

У меня есть монады, которые обертывают списки. Я хотел бы объединить эти монады, чтобы образовать монаду, которая объединяет все списки.

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

Для этого я сделал (псевдокод) :

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

Это похоже на компиляцию, но мне кажется, что это должно быть проще и короче , чем эта. Есть идеи по улучшению?

Answer 1

Есть экземпляр Traverse[List]. Каждый Monad[M] является частным случаем Applicative[M]. Поэтому, если у вас есть

List[M[List[A]]]

вы можете использовать sequence в Traverse[List] с Applicative[M], чтобы сначала преобразовать его в

M[List[List[A]]]

и затем используйте map из Functor[M] до flatten в

M[List[A]]

Что-то вроде

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

в случае Option.

Answer 2

Я думаю, что полугруппа (или SemigroupK) может быть абстракцией, которую вы ищете