Scalaz-sevenでのTraverse[List]実装の説明

Question

私は理解しようとしています traverseImpl での実装 スカラズセブン:

def traverseImpl[F[_], A, B](l: List[A])(f: A => F[B])(implicit F: Applicative[F]) = {
  DList.fromList(l).foldr(F.point(List[B]())) {
     (a, fbs) => F.map2(f(a), fbs)(_ :: _)
  }
}

誰かがどのように説明できますか List と相互作用します Applicative?最終的に、私は他のインスタンスを実装できるようにしたいと思います Traverse.

Answer 1

Applicativeを使用すると、コンテキスト内の関数をコンテキスト内の値に適用できます。たとえば、次のように適用できます some((i: Int) => i + 1) に some(3) そして、取得します some(4).今のところそれを忘れましょう。私は後でそれに戻ってくるでしょう。

リストには2つの表現があり、次のいずれかです Nil または head :: tail.あなたはそれの上に折り畳むために使用することができます foldLeft しかし、それを折りたたむ別の方法があります:

def foldr[A, B](l: List[A], acc0: B, f: (A, B) => B): B = l match {
   case Nil => acc0
   case x :: xs => f(x, foldr(xs, acc0, f))
}

与えられた List(1, 2) 右側から始まる関数を適用するリストの上に折りたたみます-私たちは本当に左側からリストを分解していますが！

f(1, f(2, Nil))

これは、リストの長さを計算するために使用できます。与えられた List(1, 2):

foldr(List(1, 2), 0, (i: Int, acc: Int) => 1 + acc)
// returns 2

これはまたに使用することができます 作成 別のリスト:

foldr[Int, List[Int]](List(1, 2), List[Int](), _ :: _)
//List[Int] = List(1, 2)

だから、空のリストと与えられた :: 機能別のリストを作成することができました。私たちの要素がいくつかの要素にある場合はどうなりますか コンテキスト?私たちの文脈がapplicativeであれば、私たちはまだ要素を適用することができます :: その文脈で。続きを読む" List(1, 2) と Option 私達のapplicativeとして。私たちはから始めます some(List[Int]())) 私達は適用したいと思います :: での機能 Option コンテキスト。これは何ですか F.map2 そうだそれは彼らの2つの値を取ります Option コンテキストに二つの引数の提供された関数を入れて、 Option コンテキストとそれらを一緒に適用します。

だから我々が持っている文脈の外に (2, Nil) => 2 :: Nil

文脈では、我々は持っている: (Some(2), Some(Nil)) => Some(2 :: Nil)

元の質問に戻る:

// do a foldr 
DList.fromList(l).foldr(F.point(List[B]())) {
  // starting with an empty list in its applicative context F.point(List[B]())
  (a, fbs) => F.map2(f(a), fbs)(_ :: _)
  // Apply the `::` function to the two values in the context
}

なぜ違いがあるのかわかりません DList が使用される。私が見ているのは、トランポリンを使用しているので、うまくいけば、スタックを吹き飛ばすことなくこの実装を機能させることができますが、私は

このような右の折り畳みを実装することについての興味深い部分は、代数的データ型のトラバースを実装するアプローチを提供すると思うことです カタモルフィズム.

例えば、与えられた:

trait Tree[+A]
object Leaf extends Tree[Nothing]
case class Node[A](a: A, left: Tree[A], right: Tree[A]) extends Tree[A]

Foldは次のように定義されます（これは実際にはforと同じアプローチに従っています List):

def fold[A, B](tree: Tree[A], valueForLeaf: B, functionForNode: (A, B, B) => B): B = {
  tree match {
    case Leaf => valueForLeaf
    case Node(a, left, right) => functionForNode(a, 
        fold(left, valueForLeaf, functionForNode), 
        fold(right, valueForLeaf, functionForNode)
      )
  }
}

そしてトラバースはそれを使うでしょう fold と F.point(Leaf) そしてそれを適用する Node.apply.ありませんが F.map3 だからそれは少し面倒かもしれません。

Answer 2

これは把握するのがとても簡単なことではありません。 マイブログ投稿の冒頭でリンクされている記事を読むことをお勧めします。 a>。

シドニーの最後の機能プログラミング会議中に主題についても発表し、スライドを見つけることができますこちら

数単語で説明しようとすると、traverseはリストの各要素を1つずつトラバースし、最終的にリスト(_ :: _)を再構築しますが、F Applicativeによって与えられるようにいくつかの種類の「効果」を累積/実行することになります。 。 FがStateの場合、それはいくつかの状態を追跡します。 FがMonoidに対応する適用である場合、リストの各要素に対してある種の測定値を集約します。

リストと適用の主な相互作用は、map2要素を受信し、F[B]の定義によってそれを他のF[List[B]]要素に添付し、一般的な関数としてFコンストラクターコードの使用によってそれを他のApplicative要素に接続します。適用する

そこから、Listの他のインスタンスを実装することは、トラバースしたいデータ構造のデータコンストラクタを::ingにしかありません。リンクされているPowerPointプレゼンテーションを見ている場合は、バイナリツリーのトラバーサルを持つスライドがいくつかわかります。

Answer 3

List#foldRight 大きなリストのスタックを吹き飛ばします。REPLでこれを試してみてください:

List.range(0, 10000).foldRight(())((a, b) => ())

通常、リストを逆にすることができます foldLeft, その後、この問題を回避するために結果を逆にします。しかし、と traverse 効果が正しく処理されるように、要素を正しい順序で処理する必要があります。 DList トランポリンのおかげで、これを行うための便利な方法です。

最後に、これらのテストは合格しなければなりません:

https://github.com/scalaz/scalaz/blob/scalaz-seven/tests/src/test/scala/scalaz/TraverseTest.scala#L13 https://github.com/scalaz/scalaz/blob/scalaz-seven/tests/src/test/scala/scalaz/std/ListTest.scala#L11 https://github.com/scalaz/scalaz/blob/scalaz-seven/core/src/main/scala/scalaz/Traverse.scala#L76