解释scalaz个

Question

我想了解scalaz-seven的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

这不太容易理解。我建议阅读my blog post on the subject开头链接的文章。

我还在悉尼上次函数编程会议上做了关于这个主题的介绍，你可以找到幻灯片here。

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

列表和应用性的主要相互作用是与map2应用中，其中它接收F[B]元素，并将其附加到其它F[List[B]]元件通过的F定义作为Applicative和使用List构造::的作为特定功能适用。

从那里你可以看到，执行其他Traverse的实例仅仅是你想要遍历的数据结构的数据构造函数的约apply。如果您查看链接的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