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

Question

我试图理解scalaz-7中的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

应用程序允许您将上下文中的函数应用于上下文中的值.因此,举例来说,你可以申请some((i: Int) => i + 1)到some(3)和得到some(4).我们暂时忘记这一点.我稍后再说.

列表有两个表示,它是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]

折叠将被定义为这样(它实际上遵循相同的方法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

这不容易掌握.我建议阅读我在博客文章开头关于这个主题的文章.

我还在悉尼的最后一次功能编程会议上做了关于这个主题的演讲,你可以在这里找到幻灯片.

如果我可以尝试用几个词来解释,traverse将逐个遍历列表中的每个元素,最终重新构建列表(_ :: _)但是累积/执行某种"效果",如下所示F Applicative.如果F是State它跟踪的一些状态.如果F对应于Monoid它的应用程序聚合了列表的每个元素的某种度量.

列表和应用性的主要相互作用是与map2那里它接收一个应用程序F[B]元件,并将它附加到另一F[List[B]]元件由定义的F作为Applicative和使用的List构造::作为特定功能适用.

从那里你可以看到实现其他实例Traverse只是关于apply你想要遍历的数据结构的数据构造函数.如果你看一下链接的powerpoint演示文稿,你会看到一些带有二叉树遍历的幻灯片.