7

我试图了解scalaz-7traverseImpl中的实现：

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). 让我们暂时忘记这一点。我稍后再谈。

List 有两种表示形式，要么是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)并Option作为我们的应用程序。我们首先some(List[Int]()))要在上下文中应用该::功能。Option这就是它的F.map2作用。它在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。我看到的是它使用了蹦床，所以希望能够在不破坏堆栈的情况下使这个实现工作，但我没有尝试过所以我不知道。

像这样实现正确折叠的有趣部分是，我认为它为您提供了一种使用catamorphisms实现代数数据类型遍历的方法。

例如给出：

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 将使用它fold并将F.point(Leaf)其应用于Node.apply. 虽然没有F.map3所以可能有点麻烦。

于 2012-03-15T07:54:22.553 回答
6

这不是那么容易掌握的东西。我建议阅读我的博客文章开头链接的文章。

在悉尼的上一次函数式编程会议上，我也做了一个关于这个主题的演讲，你可以在这里找到幻灯片。

如果我可以尝试用几句话来解释，我将一个一个traverse地遍历列表中的每个元素，最终重新构建列表(_ :: _)，但累积/执行F Applicative. 如果F是State，它会跟踪某些状态。如果F是对应于 a 的应用程序，Monoid它会为列表中的每个元素聚合某种度量。

列表和应用程序的主要交互是与map2应用程序进行交互，在该应用程序中，它接收一个F[B]元素并将其附加到其他F[List[B]]元素，定义F为 anApplicative并使用List构造函数::作为要应用的特定函数。

从那里你会看到实现其他实例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 回答