user3139545 user3139545 - 2 months ago 20
Scala Question

Implement fold with for-comprehension

How can a

fold
be implemented as a
for-comprehension
in Scala? I see the only way is to use some recursive call? This is a try that is failing, not sure how to do this? What is the best way to implement
fold
as a
for-comprehension


val nums = List(1,2,3)
nums.fold(0)(_+_)
def recFold(acc: Int = 0): Int = {
(for {
a <- nums
b = recFold(a + acc)
} yield b).head
}
recFold(0) //Stack overflow

Answer

If you really want to use for, you don't need recursion, but you would need a mutable variable:

val nums = List(1,2,3)

def recFold(zero: Int)(op: (Int, Int) => Int): Int = {
  var result: Int = zero
  for { a <- nums } result = op(result, a)
  result
}

recFold(0)(_ + _) // 6

Which is pretty similar to how foldLeft is actually implemented in TraversableOnce:

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