不了解 Scala 中 foldLeft 和 foldRight 的效率不同

Question

阅读 Scala 编程，第 2 版中的以下段落对我来说没有意义。

def flattenLeft[T](xss: List[List[T]]) =
  (List[T]() /: xss) (_ ::: _)

def flattenRight[T](xss: List[List[T]]) =
  (xss :\ List[T]()) (_ ::: _)

Because list concatenation, xs ::: ys , takes time proportional to its first argument xs, the implementation in terms of fold right in flattenRight is more efficient than the fold left implementation in flattenLeft . The problem is that flattenLeft(xss) copies the first element list xss.head n − 1 times, where n is the length of the list xss

因此，如果列表连接所花费的时间与其 first 参数成正比，这是否意味着 flattenLeft 效率更高，因为它的第一个参数是一个空列表并且flattenRight的第一个参数是未知长度的列表？

Answer 1

foldLeft的第一个参数只是开头的一个空List，即本次折叠的zero。

当您将所有 List 折叠到一个 List 时，fold 构建中间列表，其中包含每次连接的部分结果，然后用作下一个连接的参数级联。这个中间结果越来越大。在 foldLeft 上，这将是第一个参数：

 def flattenLeft[T](xss: List[List[T]]) =
   (List[T]() /: xss) ((acc, xs) => acc ::: xs )
                      //^ this one

相反，对于 foldRight 你从右边构建结果，这意味着中间结果（增长的那个）是右边的，这将是连接操作的第二个参数

def flattenRight[T](xss: List[List[T]]) =
   (xss :\ List[T]()) ((xs, acc) =>  xs ::: acc)
                            //^ this one gets bigger now

因此，flattenRight 将花费更少的时间，因为连接的第一个参数不会随着您的进展而增长。

Answer 2

通过从左侧折叠来展平列表

[ [....] [....] [....] [....] [....] ]
  [....] 
  [...........] 
  [..................] 
  [.........................] 
  [................................]

从右边开始为

[ [....] [....] [....] [....] [....] ]
                              [....] 
                       [...........]  
                [..................]  
         [.........................]  
  [................................]

当从左边折叠 n 个列表时，第一个列表中的每个元素被跟踪 (n-1) 次；在第二个列表中 (n-2) 次，等等。这是经典的二次行为。

当从右侧折叠时，每个元素都被精确地追踪一次，以获得整个操作的线性行为。

不了解 Scala 中 foldLeft 和 foldRight 的效率不同

Don't understand efficiency is different in foldLeft and foldRight in Scala

scala

fold