使用foldRight反转列表的优雅方式？

Question

我在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？
• 有没有更好的方法可以不使用:::？

Answer 1

由于标准库中的foldRighton 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的缓慢实现,因为它将列表折叠两次.但:

1. 无论如何,"两次"是一个常数因子,所以它渐近地等同于折叠一次.
2. 无论如何,你必须两次查看列表.一旦将计算推入堆栈并再次将它们从堆栈中弹出.
3. foldRight上面的实现比标准库中的实现更快.