Is there a way to flatten nested monads of different types?

Question

I am not sure how to describe this problem, so I'll just show the type signatures.

I have an instance of the following:

val x:Future[F[Future[F[B]]]] = ???

And I want an instance of:

val y:Future[F[B]] = ???

F is a Monad, so I have the following methods:

def pure[A](a:A):F[A] = ???
def flatMap[A, B](fa:F[A], f:A => F[B]):F[B] = ???
def map[A, B](fa:F[A], f:A => B):F[B] = flatMap(fa, (a:A) => pure(f(a)))

I think the following should work, but it does not feel right:

x.flatMap { fWithFuture =>
  val p = Promise[F[B]]
  flatMap(fWithFuture, (futureF: Future[F[B]]) => {
    p.completeWith(futureF)
    pure(())
  })
  p.future
}

Is there a concept I'm missing?

A bit of background information. I am trying to define a function like this:

def flatMap[A, B](fa:Future[F[A]], f: A => Future[F[B]]):Future[F[B]] = ???

Maybe this is conceptually a weird thing. Any tips on useful abstractions are welcome.

Answer 1

As Rex Kerr notes above, you can often use a monad transformer to deal with a situation where you find yourself with alternating layers like this. For example, if F here is Option, you could use Scalaz 7.1's OptionT monad transformer to write your flatMap:

import scalaz._, Scalaz._

type F[A] = Option[A]

def flatMap[A, B](fa: Future[F[A]], f: A => Future[F[B]]): Future[F[B]] =
  OptionT(fa).flatMap(f andThen OptionT.apply).run

OptionT[Future, A] here is a kind of wrapper for Future[Option[A]]. If your F is List, just replace OptionT with ListT and run with underlying (and so on).

The nice thing is that when you're working with OptionT[Future, A], for example, you can generally avoid ending up with Future[Option[Future[Option[A]]]] in the first place—see my answer here for some more detailed discussion.

One drawback is that not all monads have transformers. For example, you can put Future at the bottom of the stack (as I've done above), but there's not really a useful way to define FutureT.

Answer 2

This may answer the "And I want an instance of:" part.

$ scala
Welcome to Scala version 2.10.4 (Java HotSpot(TM) 64-Bit Server VM, Java 1.8.0_05).
Type in expressions to have them evaluated.
Type :help for more information.

scala> import scala.concurrent.Future
import scala.concurrent.Future

scala> import scala.concurrent.ExecutionContext.Implicits.global
import scala.concurrent.ExecutionContext.Implicits.global

scala> Future(List(Future(1),Future(2),Future(3))) // Future[F[Future[B]]]
res0: scala.concurrent.Future[List[scala.concurrent.Future[Int]]] = scala.concurrent.impl.Promise$DefaultPromise@41ab013

scala> res0.map(Future.sequence(_)) // transformed to Future[Future[F[B]]
res1: scala.concurrent.Future[scala.concurrent.Future[List[Int]]] = scala.concurrent.impl.Promise$DefaultPromise@26a4842b

scala> res1.flatMap(identity) // reduced to Future[F[B]]
res2: scala.concurrent.Future[List[Int]] = scala.concurrent.impl.Promise$DefaultPromise@4152d38d

Hopefully the below flatMap definition should give an idea of transforming the types :) I replaced F with a List type for ease of understanding.

scala>   def flatMap[A, B](fa:Future[List[A]], f: A => Future[List[B]]):Future[List[B]] = {
     |     val x: Future[List[Future[List[B]]]] = fa.map(_.map(f))
     |     val y: Future[Future[List[List[B]]]] = x.map(Future.sequence(_))
     |     val z: Future[Future[List[B]]] = y.map(_.map(_.flatten))
     |     z.flatMap(identity)
     |   }
flatMap: [A, B](fa: scala.concurrent.Future[List[A]], f: A => scala.concurrent.Future[List[B]])scala.concurrent.Future[List[B]]