How to understand traverse, traverseU and traverseM

Question

I am confused about the usage case about traverse, traverseU and traverseM, I searched it in the scalaz website, the simple code example:

 def sum(x: Int) = x + 1

 List(1,2,3).traverseU(sum)

it looks like it is similar to (map and aggregate):

List(1,2,3).map(sum).reduceLeft(_ + _)

I think it is more than that for traverseU, I just wonder what is the difference between those 3 method, it would be better I will have some sample code to show the difference

Many thanks in advance

Solution

sequence is used to gather together applicative effects. More concretely, it lets you "flip" F[G[A]] to G[F[A]], provided G is Applicative and F is Traversable. So we can use it to "pull together" a bunch of Applicative effects (note all Monads are Applicative):

List(Future.successful(1), Future.successful(2)).sequence : Future[List[Int]]
// = Future.successful(List(1, 2))
List(4.set("abc"), 5.set("def")).sequence : Writer[String, List[Int]]
// = List(4, 5).set("abcdef")

traverse is equivalent to map then sequence, so you can use it when you have a function that returns an Applicative and you want to just get a single instance of your Applicative rather than a list of them:

def fetchPost(postId: Int): Future[String]
//Fetch each post, but we only want an overall `Future`, not a `List[Future]`
List(1, 2).traverse[Future, String](fetchPost): Future[List[String]]

traverseU is the same operation as traverse, just with the types expressed differently so that the compiler can infer them more easily.

def logConversion(s: String): Writer[Vector[String], Int] =
  s.toInt.set(Vector(s"Converted $s"))
List("4", "5").traverseU(logConversion): Writer[Vector[String], List[Int]]
// = List("4", "5").map(logConversion).sequence
// = List(4.set("Converted 4"), 5.set("Converted 5")).sequence
// = List(4, 5).set(Vector("Converted 4", "Converted 5"))

traverseM(f) is equivalent to traverse(f).map(_.join), where join is the scalaz name for flatten. It's useful as a kind of "lifting flatMap":

def multiples(i: Int): Future[List[Int]] =
  Future.successful(List(i, i * 2, i * 3))
List(1, 10).map(multiples): List[Future[List[Int]]] //hard to work with
List(1, 10).traverseM(multiples): Future[List[Int]]
// = List(1, 10).traverse(multiples).map(_.flatten)
// = List(1, 10).map(multiples).sequence.map(_.flatten)
// = List(Future.successful(List(1, 2, 3)), Future.successful(List(10, 20, 30)))
//     .sequence.map(_.flatten)
// = Future.successful(List(List(1, 2, 3), List(10, 20, 30))).map(_.flatten)
// = Future.successful(List(1, 2, 3, 10, 20, 30))

Comments

[Xiaohe Dong]

thanks, I upvote, so I just wonder you mentioned that the difference between traverse and traverseU is the type inference, is this only difference, because as far as I am concerned, I will only use traverseU instead of traverse

[lmm]

Yes, that's the only difference. (Technically it uses an extra parameter to perform the inference, but I'd expect the JVM to optimize this away). In the case where traverseU doesn't infer the type parameters and you need to specify them by hand (or if you're writing generic code where the type you're traversing is itself a type parameter), it's easier to do with traverse (which doesn't have the inference helper), but I think that's the only case where you'd ever want to use traverse rather than traverseU

[Xiaohe Dong]

BTW, I think the code should be Future.now instead of Future.successful, because the previous one is from scalaz, so it will have implicit value, but the later one from standard library does not have implicit resolution

[lmm]

I believe there are instances for the standard library Future if you have the appropriate imports in scope (from somewhere in scalaz.std).