解释scalaz-7中的Traverse [List]实现

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

这可用于计算列表的长度.给定清单(1,2)：

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

这也可以用于创建另一个列表：

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

因此,给定一个空列表和:: function,我们可以创建另一个列表.如果我们的元素在某些情况下怎么办？如果我们的上下文是一个应用程序,那么我们仍然可以在该上下文中应用我们的元素和::.继续列表(1,2)和选项作为我们的应用程序.我们从一些(List [Int]()))开始,我们想在Option上下文中应用:: function.这就是F.map2的作用.它在Option上下文中需要两个值,将两个参数的提供函数放入Option上下文并将它们一起应用.

所以在上下文之外我们有(2,Nil)=> 2 ::无

在上下文中,我们有:(一些(2),一些(无))=>一些(2 ::零)

回到最初的问题：

// 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)(_ :: _)
  // 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]

折叠将被定义为这样(它实际上遵循与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,functionForNode)
      )
  }
}

并且遍历将使用F.point(Leaf)的折叠并将其应用于Node.apply.虽然没有F.map3所以它可能有点麻烦.