7

私はscalaz-seventraverseImplの実装を理解しようとしています：

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。

4

3 に答える 3

9

アプリカティブを使用すると、コンテキスト内の関数をコンテキスト内の値に適用できます。したがって、たとえば、に適用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)

したがって、空のリストと::関数を指定すると、別のリストを作成できました。要素が何らかのコンテキストにある場合はどうなるでしょうか? コンテキストが適用可能である場合でも、要素を::そのコンテキストで適用できます。List(1, 2)andを applicative として続けOptionます。コンテキストで関数some(List[Int]()))を適用することから始めます。これが の機能です。コンテキストで2 つの値を取り、提供された 2 つの引数の関数をコンテキストに入れ、それらを一緒に適用します。::OptionF.map2OptionOption

だから私たちが持っている文脈の外で(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)
      )
  }
}

traverse はそれをfoldwithで使用しF.point(Leaf)、 to に適用しますNode.apply。ないF.map3ので少し面倒かもしれませんが。

于 2012-03-15T07:54:22.553 に答える
6

これはそう簡単に把握できるものではありません。件名に関する私のブログ投稿の冒頭にリンクされている記事を読むことをお勧めします。

前回シドニーで開催された関数型プログラミングの会議でも、このテーマに関するプレゼンテーションを行いました。スライドはこちらからご覧いただけます。

簡単に説明すると、traverseはリストの各要素を 1 つずつトラバースし、最終的にリストを再構築します(_ :: _)が、F Applicative. ある場合FはState、何らかの状態を追跡します。Fが a に対応するアプリカティブである場合Monoid、リストの各要素に対して何らかの種類の尺度を集約します。

リストと applicative の主な相互作用は、要素をmap2受け取り、as の定義と適用する特定の関数としてのコンストラクターの使用によってF[B]他の要素にアタッチするアプリケーションとのやり取りです。F[List[B]]FApplicativeList::

そこから、 の他のインスタンスを実装することは、走査したいデータ構造のデータ コンストラクターを ing することTraverseだけであることがわかります。applyリンクされた PowerPoint プレゼンテーションを見ると、バイナリ ツリー トラバーサルを含むいくつかのスライドが表示されます。

于 2012-03-15T05:31:18.013 に答える
2

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

于 2012-03-15T21:50:24.277 に答える