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

Question

我在 Programming in Scala 中阅读了有关折叠技术的信息书并遇到了这个片段:

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

如您所见，它是使用 foldLeft 完成的。或 /:运算符(operator)。好奇如果我使用 :\ 做它会是什么样子，我想出了这个:

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

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

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

在不使用 ::: 的情况下，是否有更好的方法来做到这一点？ ?

Answer 1

自 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的实现以上比标准库中的要快。