5

在Eric Torreborre关于迭代器模式本质一文的博文中，他描述了遍历的笛卡尔积如何也是遍历。

谁能给我看一个使用scalaz 库的例子，因为我不知道。假设问题是，对于List[Int]我想提供以下两者：

  1. Int列表中元素的总和
  2. AList[String]其元素是通过将“Z”附加到Ints的字符串表示来创建的

我的理解是，我可以使用traverse但仅实际遍历我的结构一次的方式来执行此操作，这与此解决方案不同：

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

注意 1 -我知道还有其他方法可以做到这一点，我不需要遍历这个例子，也不一定是最清晰的解决方法。但是，我正在尝试理解 traverse，因此我真的在寻找所述问题的答案

编辑- 感谢下面的missingfaktor展示了如何使用State. 我想我想知道的是如何组合这两个独立的计算。例如; 我的功能理论上如下：

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

我想拥有这些相互独立的积累机制，然后选择是List[Int]使用它们中的一个还是两个来遍历我。我想象一些代码有点像这样：

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

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

Eric 暗示这是可能的，但我不知道该怎么做~ 即我不知道如何定义shape和accum以一种可以组合它们的方式，也不知道如何组合它们。

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

4

4 回答 4

4

我在 Jason 的基础上添加了我自己的答案，以显示遍历列表的不同方式：

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"))
  }
}

我认为最后一个示例显示了您所追求的：2 个独立定义的函数，它们可以组合成只进行一次遍历。

于 2012-02-07T05:49:50.160 回答
3

Debasish Ghosh 写了一篇关于这个主题的好文章。根据该帖子中的代码：

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))

编辑：

你有两个函数List[A] => B和List[A] => C，你想要一个函数List[A] => (B, C)。这&&&就是为了。不过，这不会融合循环。我无法想象如何在这种情况下融合循环。

Fwiw，代码：

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)

编辑2：

如果你有函数A => B，A => C你可以将它们合并到A => (B, C)using 中&&&。现在 ifB : Monoid和C : Monoid，您可以使用foldMapget List[A] => (B, C)。这将在一个循环中完成。

代码：

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))

最终编辑：（我发誓我不会再编辑了。）

Haskell由于这些概念起源于 Haskell，我认为在标签下重新发布这个问题是个好主意，我做到了。那里的答案似乎与我在此线程中所说的一致。希望这可以帮助。

于 2012-02-06T15:42:11.453 回答
3

您在这里看不到大的胜利，因为您只是将普通的 Monoids 推广到 Applicatives 中，因此您将它们融合在一起。

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")

不妨只Monoid[(Int, List[String])]用于所述问题：

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")

如果您要遍历的效果之一是非平凡的 Applicative，例如State.

于 2012-02-06T22:41:54.290 回答
2

如果我正确理解你，你正在寻找的应该在 scala-7 分支示例中描述：WordCount。它还涉及状态。我在手机上，否则我会提供链接。

这是链接：

HTH安德烈亚斯

编辑：

好的，还有一些解释。我认为您的问题的根本问题是如何编写函数或应用程序。这可以通过应用程序上的产品方法来实现。

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

所以你需要为你的两个函数 shape 和 accum 定义 applicative。accum 将被建模为州应用程序。

如果我们从示例中查看这一行： val WordCount = StateT.stateMonad[Int].compose({type λ[α] = Int})#λ

它创建了一个“有效”的应用程序（对不起，我的措辞不好）。通常在遍历时你只有当前元素而已。但是如果你想在之前的计算上进行计算，你需要状态，所以这会创建一个状态应用程序，它为它遍历的每个元素返回 1（参见 Monoid[Int].applicative）。

现在要做一些实际的事情，我们需要查看 atWordStart 方法，并且您需要定义一个可以与构造的 WordCount 应用程序一起使用的方法（使用状态）

这是 scalaz 6 中的另一个示例，它更简单。我认为观察 initialValue 以及 transform1 方法的作用很重要：

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
  }
}

我现在记得是因为这个话题我也很感兴趣。我问为什么 eric 在他的博文中没有提供应用产品。他说他放弃了与类型签名的斗争。围绕那个时候 jason 修复了 scalaz7 的 WordCount 示例（六个示例没有提供动作计数词）

于 2012-02-06T16:30:31.577 回答