Cartesian product traverse in scalaz

问题:

In Eric Torreborre's blogpost on the paper Essence of the Iterator Pattern, he describes how the cartesian product of a traverse is also a traverse.

Can anyone show me an example of this using the scalaz library as I can't figure it out. Let's say the problem is that, for a List[Int] I want to provide both of:

1. The Int sum of the elements in the list
2. A List[String] the elements of which are created by appending the "Z" to the String representation of the Ints

My understanding is that I can do this using traverse but in such a way as to only actually traverse my structure once, unlike this solution:

val xs = List(1, 2, 3, 4)
val (sum, strings)  = (xs.sum, xs map (_.toString + "Z"))

NOTE 1 - I know that there are other ways of doing this and that I neither need traverse for this example, and nor is traverse even necessarily the clearest way to solve it. I am, however, trying to understand traverse, so am really looking for the answer to the question as stated

---

EDIT - thanks to missingfaktor below for showing how to do this using State. I guess what I want to know is how I can compose the two independent calculations. For example; my functions are notionally as follows:

val shape = (_ : List[Int]) map (_.toString + "Z")
val accum = (_ : List[Int]).sum

I want to have these mechanisms of accumulation independently of one another and then choose whether to traverse my List[Int] using either or both of them. I imagined some code a bit like this:

xs traverse shape //A List[String]
xs traverse accum //An Int

xs traverse (shape <x> accum) //The pair (List[String], Int)

Eric implies that this is possible but I don't get how to do it ~ i.e. I don't see how to define shape and accum in such a way as that they can be composed, nor how to compose them.

NOTE 2 that shape and accum are not meant to literally be the functions with the signatures as above. They are expressions which have the type necessary to perform the above traversals.

回答1:

I'm adding my own answer, building on Jason's one, to show different ways of traversing the list:

import org.specs2._
import scalaz.std.anyVal._, scalaz.std.list._
import scalaz._, std.tuple._
import scalaz.{Monoid, Applicative}

class TraverseSpec extends mutable.Specification {

  implicit val Sum = Monoid[Int].applicative
  implicit val Concat = Monoid[List[String]].applicative
  implicit val A: Applicative[({type λ[α] = (Int, List[String])})#λ] = Sum.product[({type λ[α]=List[String]})#λ](Concat)
  val xs = List(1, 2, 3, 4)

  "traverse - by folding the list with a Monoid" >> {
    val (sum, text) = Foldable[List].foldMap(xs)(a => (a, List(a.toString + "Z")))
    (sum, text) === (10, List("1Z", "2Z","3Z", "4Z"))
  }
  "traverse - with a function returning a tuple" >> {
    val (sum, text) = A.traverse(xs)(a => (a, List(a.toString + "Z")))
    (sum, text.reverse) === (10, List("1Z", "2Z","3Z", "4Z"))
  }
  "traverse - with 2 functions and 2 traversals" >> {
    val count   = (a: Int) => a
    val collect = (a: Int) => List(a.toString+"Z")

    val sum  = Sum.traverse(xs)(count)
    val text = Concat.traverse(xs)(collect)

    (sum, text.reverse) === (10, List("1Z", "2Z","3Z", "4Z"))
  }
  "traverse - with 2 functions and 1 fused traversal" >> {
    val sum     = (a: Int) => a
    val collect = (a: Int) => List(a.toString+"Z")

    implicit def product[A, B, C](f: A => B): Product[A, B] = Product(f)
    case class Product[A, B](f: A => B) {
      def <#>[C](g: A => C) = (a: A) => (f(a), g(a))
    }

    val (total, text)  = A.traverse(xs)(sum <#> collect)
    (total, text.reverse) === (10, List("1Z", "2Z","3Z", "4Z"))
  }
}

I think that the last example shows what you're after: 2 independently defined functions which can be composed to do just one traversal.

回答2:

Debasish Ghosh has written a nice post on this topic. Based on the code in that post:

scala> List(1, 2, 3, 4)
res87: List[Int] = List(1, 2, 3, 4)

scala> .traverse[({ type L[X] = State[Int, X] })#L, String] { cur =>
     |   state { (acc: Int) => (acc + cur, cur.toString + "Z") }
     | }
res88: scalaz.State[Int,List[String]] = scalaz.States$$anon$1@199245

scala> .apply(0)
res89: (Int, List[String]) = (10,List(1Z, 2Z, 3Z, 4Z))

Edit:

You have two functions List[A] => B and List[A] => C, and you want a function List[A] => (B, C). That's what &&& is for. This won't fuse the loops though. I cannot imagine how it can be possible to fuse loops for such a case.

Fwiw, code:

scala> val shape = (_ : List[Int]) map (_.toString + "Z")
       val accum = (_ : List[Int]).sum
shape: List[Int] => List[java.lang.String] = <function1>
accum: List[Int] => Int = <function1>

scala> val xs = List(1, 2, 3, 4)
xs: List[Int] = List(1, 2, 3, 4)

scala> (shape &&& accum) apply xs
res91: (List[java.lang.String], Int) = (List(1Z, 2Z, 3Z, 4Z),10)

Edit 2:

If you have functions A => B and A => C you can merge them into A => (B, C) using &&&. Now if B : Monoid and C : Monoid, you can use foldMap to get List[A] => (B, C). This will do the stuff in one loop.

Code:

scala> val f: Int => Int = identity
f: Int => Int = <function1>

scala> val g: Int => List[String] = i => List(i.toString + "Z")
g: Int => List[String] = <function1>

scala> List(1, 2, 3, 4).foldMap(f &&& g)
res95: (Int, List[String]) = (10,List(1Z, 2Z, 3Z, 4Z))

Final edit: (I swear I am not editing this again.)

Since these concepts have their origins in Haskell, I thought it'd be a good idea to re-post this question under Haskell tag, and I did. The answer there seems to be consistent with whatever I have said in this thread. Hôpe this helps.

回答3:

You don't see a big win here, as you're just promoting plain ol' Monoids into Applicatives so you fuse them together.

import scalaz.std.anyVal._, scalaz.std.list._, scalaz.std.string._
val Sum = Monoid[Int].applicative
val Concat = Monoid[List[String]].applicative
val A: Applicative[({type λ[α] = (Int, List[String])})#λ] = Sum.product[({type λ[α]=List[String]})#λ](Concat)

val xs = List(1, 2, 3, 4)
val (sum, text) = A.traverse(xs)(a => (a, List(a.toString + "Z")))
println(sum, text) // 10, List("1Z", "2Z", "3Z", "4Z")

Might as well just use Monoid[(Int, List[String])] for the stated problem:

import scalaz._, std.tuple._
val (sum1, text1) = Foldable[List].foldMap(xs)(a => (a, List(a.toString + "Z")))
println(sum1, text1) // 10, List("1Z", "2Z", "3Z", "4Z")

Things get more interesting if one of the effects you want to traverse with is a non-trivial Applicative, like State.

回答4:

If I understand you correctly that what you are looking for should be described in the scala-seven branch example: WordCount. It also involves state. I'm on mobile otherwise I would provide link.

Here's the links:

• Scalaz 6
• Scalaz 7

HTH Andreas

EDIT:

Ok some more explanations. I think the fundamental problem of your questions is how to compose functions or therefor applicative. This can be achieved through the product method on applicative.

https://github.com/scalaz/scalaz/blob/scalaz-seven/core/src/main/scala/scalaz/Applicative.scala#L46

So you need to define applicative for your two functions shape and accum. Where accum would be modeled as a state applicative.

If we look at this line form the example: val WordCount = StateT.stateMonad[Int].compose({type λ[α] = Int})#λ

It creates an applicative which 'works' (sorry my poor wording) which state. Usually on traverse you have only the current element nothing more. But if you want to compute on previous computations you need state so this create an state-applicative which returns 1 for each element it traverses ( see Monoid[Int].applicative).

Now to DO actually something we need to look at the atWordStart Method and you need to define a method which can work with the constructed WordCount applicative (using State)

Here is another example from scalaz 6, which is more simple. I think its important to observe the initialValue and how the transform1 method does :

import scalaz._
import Scalaz._

object StateTraverseExample {

  type StS[x] = State[(Set[Int], Boolean), x] 

  def main(args: Array[String]): Unit = {
    println("apparently it works " + countAndMap(Vector.range(0, 20)))
  }

  def transform1(i: Int, l: Set[Int], result: Boolean): (Set[Int],Boolean) = {
    if (result || (l contains i))
      (l, true)
    else
      (l + i, false)
   }

  def countAndMap(l: Vector[Int]): (Set[Int],Boolean) = {
    val initialValue=(Set.empty[Int], false)

    val counts = l.traverse[StS, Unit] { i => 
      state { case (set, result) => (transform1(i,set,result), println(i))   }
    } ~> initialValue
    counts
  }
}

I remember now because the topic interested me too. I asked why eric in his blogpost did not provide the applicative product. He said he it gave up wrestling with the type signatures. Arround that time jason fixed the WordCount example for scalaz7 ( six example did not provide action counting word)