Scala中foldLeft的实现

Question

TraversableOnce 用可变的 var result 实现了 foldLeft 。

def foldLeft[B](z: B)(op: (B, A) => B): B = {
   var result = z
   this foreach (x => result = op(result, x))
   result
}

我知道使用递归实现foldLeft并不实用。现在我想知道是否有可能在没有可变变量的情况下高效地实现foldLeft。

它是否可以做到？如果不能，为什么？

- Michael

Answer 1

尾递归是你的朋友：

def foldLeft[A, B](xs: Seq[A], z: B)(op: (B, A) => B): B = {
  def f(xs: Seq[A], acc: B): B = xs match {
    case Seq()   => acc
    case x +: xs => f(xs, op(acc, x))
  }
  f(xs, z)
}

顺便说一下，TraversableOnce没有实现head或tail，访问元素的唯一方法是使用foreach。

- kiritsuku

Answer 2

object FoldImplement:
  def myFoldLeft(lst: List[Int])(acc: Int)(f: (Int, Int)=>Int): Int =
    lst match
      case List() => acc
      case hd::tl => myFoldLeft(tl)(f(hd,acc))(f)

  @main def runFoldImpl =
    println(myFoldLeft(List(1,3,5))(0)((acc,elem)=>acc+elem))

- Mark Grechanik

---

目前你的回答不够清晰，请编辑并添加更多细节，以帮助其他人理解它如何回答问题。你可以在帮助中心找到有关如何编写好答案的更多信息。 - Community

Answer 3

def foldLeft[B](z: B)(op: (B, A) => B): B = {
  val thislist = this.toList
  @tailrec
  def myFold(result: B, list: List[A]): B = list match {
    case Nil => result
    case head :: tail => myFold(op(result,head), tail)
  }
  myFold(z, thislist)
}

- Jasper-M

---

除非集合是List，否则toList操作需要O(n)的时间复杂度。因此，这不是一种高效的解决方案。 - Nikita Volkov

所以foldLeft仍然是O(n) :p 就像sschaef所说，在TraversableOnce中访问元素的唯一方式是foreach，所以当你真正想要递归时，你必须牺牲一些效率... - Jasper-M

因此，对于这个问题的完整答案是：可以以最有效的方式实现foldLeft而不使用可变变量，但由于缺乏O(1)头和尾函数，无法在TraversableOnce中实现。 - Jasper-M

你可能应该将这个加入到你的答案中。 - Nikita Volkov

使用 toIterator 时，开销不应该更低吗？ - Kigyo