5

論文Essenceofthe IteratorPatternに関するEricTorreborreのブログ投稿で、彼はトラバースのデカルト積がトラバースでもあることを説明しています。

私には理解できないので、誰かがscalazライブラリを使用してこの例を見せてもらえますか？List[Int]問題は、私が次の両方を提供したいということだとしましょう。

  1. リスト内の要素のInt合計
  2. その要素は、 sのList[String]文字列表現に「Z」を追加することによって作成されますInt

私の理解では、これを使用してこれを行うことができますtraverseが、このソリューションとは異なり、実際に構造を1回だけトラバースするような方法で行うことができます。

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

注1-これを行うには他の方法があり、この例ではトラバースする必要はなく、トラバースは必ずしもそれを解決するための最も明確な方法でもありません。しかし、私はトラバースを理解しようとしているので、述べられているように質問に対する答えを本当に探しています

編集-を使用してこれを行う方法を示してくれた以下のmissingfaktorStateに感謝します。私が知りたいのは、2つの独立した計算をどのように構成できるかということだと思います。例えば; 私の関数は概念的に次のとおりです。

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)

エリックはこれが可能であることを暗示していますが、私はそれを行う方法がわかりません〜つまり、それらを構成できるように定義する方法shapeやaccum、それらを構成する方法がわかりません。

注2 は、文字通り上記のシグニチャを持つ関数であることを意味するものではありませんshape。accumこれらは、上記のトラバーサルを実行するために必要なタイプの式です。

4

4 に答える 4

4

リストをたどるさまざまな方法を示すために、ジェイソンの回答に基づいて独自の回答を追加しています。

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つの独立して定義された関数は、1回のトラバーサルを行うように構成できます。

于 2012-02-07T05:49:50.160 に答える
3

ここでは、単純なモノイドをアプリケーションに昇格させ、それらを融合させるだけなので、大きな勝利は見られません。

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

トラバースしたい効果の 1 つが のような自明でない Applicative である場合、事態はさらに興味深いものになりますState。

于 2012-02-06T22:41:54.290 に答える
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))

編集：

と の 2 つの関数が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あり、それらをusingA => Cにマージできる場合。との場合、 を使用して を取得できます。これにより、1つのループで処理が行われます。A => (B, C)&&&B : MonoidC : MonoidfoldMapList[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 に答える
2

あなたが探しているものは、scala-7 ブランチの例で説明する必要があることを正しく理解している場合: WordCount. 状態も含まれます。私は携帯電話を使用しています。それ以外の場合は、リンクを提供します。

リンクは次のとおりです。

HTH アンドレアス

編集：

いくつかの説明があります。あなたの質問の根本的な問題は、関数を構成する方法、またはそのために適用可能であると思います。これは、applicative の product メソッドによって実現できます。

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

したがって、2 つの関数 shape と accum の applicative を定義する必要があります。accum は状態アプリケーションとしてモデル化されます。

この行を例から見てみましょう: val WordCount = StateT.stateMonad[Int].compose({type λ[α] = Int})#λ

それは、「機能する」（申し訳ありませんが私の貧弱な言葉遣い）どの状態のアプリカティブを作成します。通常、トラバースでは、現在の要素しかありません。しかし、以前の計算で計算したい場合は、状態が必要なので、通過する各要素に対して 1 を返す状態アプリケーションを作成します (Monoid[Int].applicative を参照)。

実際に何かを行うには、atWordStart メソッドを確認する必要があり、構築された WordCount アプリケーション (State を使用) で動作するメソッドを定義する必要があります。

これは 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 の例を修正しました (6 つの例ではアクション カウント ワードが提供されませんでした)。

于 2012-02-06T16:30:31.577 に答える