笛卡尔产品遍历斯卡拉 [英] Cartesian product traverse in scalaz

问题描述

在论文< Eric Torreborre的博文上<他介绍了笛卡尔积（Cartesian product）是如何在一个笛卡尔积一个遍历也是一个遍历。

任何人都可以使用 scalaz库，因为我无法弄清楚。假设问题在于，对于 List [Int] ，我想提供以下两项：

1. Int 列表中元素的总和


2. A List [String] 其元素是通过将Z附加到 Int s

我的理解是，我可以使用遍历来做到这一点，但这样做只能实际上遍历我的结构，这个解决方案：

pre $ val $ x $ = $ $ $ $ b $ val（sum，strings） =（xs.sum，xs map（_.toString +Z））

注1 - 我知道还有其他方法可以做到这一点，我不需要遍历这个例子，也不需要遍历它来解决它。然而，我正在试图理解遍历，所以我真的正在寻找所述问题的答案

---

EDIT - 感谢下面的 missingfaktor ，以显示如何使用 State 执行此操作。我想我想知道的是我如何构成两个独立的计算。例如;我的功能在理论上如下所示：

  val shape =（_：List [Int]）map （_.toString +Z）
 val accum =（_：List [Int]）。sum 
  

我希望独立地使用这些累积机制，然后选择是否遍历我的 List [Int] ，使用<他们既可以或两者。我想像一些代码有点像这样：

$ p $ x code> xs遍历形状// A List [String]
xs遍历accum //一个Int

xs遍历（shape< x> accum）//该对（List [String]，Int）

Eric表示这是可能的，但我不知道该怎么做〜即我看不到如何定义 shape 和 accum ，这样就可以组成它们，也不用编写它们。

注2 shape 和 accum 并不意味着从字面上看就是具有上述签名的函数。它们是具有执行上述遍历所必需的类型的表达式。

解决方案

，建立在Jason的基础上，展示遍历列表的不同方式：

  import org.specs2._ 
 import scalaz.std.anyVal._，scalaz.std.list._ 
 import scalaz._，std.tuple._ 
 import scalaz。{Monoid，Applicative} 
 
 class TraverseSpec扩展mutable.Specification {
 
隐式val Sum = Monoid [Int] .applicative 
隐式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）
 
遍历 - 通过用Monoid折叠列表>> {
 val（sum，text）= Foldable [List] .foldMap（xs）（a =>（a，List（a.toString +Z）））
（sum，text） ===（10，List（1Z，2Z，3Z，4Z））
} 
遍历 - 带返回元组的函数>> {
 val（sum，text）= A.traverse（xs）（a =>（a，List（a.toString +Z）））
（sum，text.reverse）= ==（10，List（1Z，2Z，3Z，4Z））
} 
遍历 - 带2个函数和2遍历>> {
 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））
} 
遍历 - 带2个函数和1个融合遍历>> {
 val sum =（a：Int）=> a 
 val collect =（a：Int）=>列表（a.toString +Z）
 
隐式def产品[A，B，C]（f：A => B）：产品[A，B] =产品（f）
案例类别产品[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））
} 
} 
  

我认为最后一个例子显示了你后面的内容：2个独立定义的函数，它们可以组成一个遍历。

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.

解决方案

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.

这篇关于笛卡尔产品遍历斯卡拉的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！