scala - 使用foldRight反转列表的优雅方法？

我在Programming in Scala书中阅读了有关折叠技术的内容，并遇到了以下片段:

def reverseLeft[T](xs:List[T]) = (List[T]() /: xs) {
    (y,ys) => ys :: y
}

如您所见，它是使用foldLeft或/:运算符完成的。很好奇，如果我使用:\看起来会怎样，我想到了:

def reverseRight[T](xs:List[T]) = (xs :\ List[T]()) {
    (y,ys) => ys ::: List(y)
}

据我了解，:::似乎没有::快，并且线性开销取决于操作数列表的大小。诚然，我没有CS的背景，也没有FP的经验。所以我的问题是:

您如何识别/区分问题方法中的foldLeft/foldRight？

不使用:::是否有更好的方法呢？

最佳答案

由于标准库中foldRight上的List是严格的，并且是使用线性递归实现的，因此通常应避免使用它。 foldRight的迭代实现如下:

def foldRight[A,B](f: (A, B) => B, z: B, xs: List[A]) =
  xs.reverse.foldLeft(z)((x, y) => f(y, x))

foldLeft的递归实现可能是这样的:

def foldLeft[A,B](f: (B, A) => B, z: B, xs: List[A]) =
  xs.reverse.foldRight(z)((x, y) => f(y, x))

因此，您会看到，如果两者都是严格的，那么foldRight和foldLeft中的一个或另一个将通过reverse实现(无论如何在概念上)。由于列表的构建方式是在右侧关联::，因此简单的迭代折叠将是foldLeft，而foldRight只是“先反转再将foldLeft”。

直观地，您可能会认为这是foldRight的缓慢实现，因为它将列表折叠了两次。但:

无论如何，“两次”是一个恒定因子，因此在渐近上等效于折叠一次。

无论如何，您必须两次浏览该列表。一次将计算插入堆栈，然后再次将其弹出堆栈。

上面foldRight的实现比标准库中的实现更快。

关于scala - 使用foldRight反转列表的优雅方法？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/3127793/