why foldLeft can return a String type?
Again, look at the type signature:
sealed trait List[+A] {
def foldLeft[B](z: B)(op: (B, A) => B): B
}
Is very similar to fold
, but in this case B
is a free variable, it doesnât have to have any kind of relationship with A
, thus it can just infer String
why foldRight get the same result as foldLeft? I expect it to be 4123.
Classical misconception, both foldLeft
& foldRight
iterate the List
from left to right, what changes are the association order.
If you have: List(1, 2, 3)
and you fold it with 0
as the initial value and +
as the combine operation then the program will behave like this:
// For foldLeft:
((0 + 1) + 2) + 3
// For foldRight:
1 + (2 + (3 + 0))
// PS: Note how List(1, 2, 3) is just:
1 :: 2 :: 3 :: Nil
// And how :: naturally associates to the right so:
1 :: (2 :: (3 :: Nil))
// Replace :: with + and Nil with 0 and you get the same expression as before.
// That is why calling foldRight with Nil and :: gets you back the same list.
// And doing the same with foldLeft reverses it.
// BTW, this also shows that if the combine operation follows the associativity law,
// then both foldLeft and folRight will produce the same result, which is the case with the integer addition.
This can become clearer when you see their implementations.
def foldRight[A, B](list: List[A])(z: B)(op: (A, B) => B): B =
list match {
case head :: tail => op(head, foldRight(tail)(z)(op))
case Nil => z
}
def foldLeft[A, B](list: List[A])(z: B)(op: (B, A) => B): B = {
@annotation.tailrec
def loop(remaining: List[A], acc: B): B =
remaining match {
case head :: tail => loop(remaining = tail, acc = op(acc, head))
case Nil => acc
}
loop(remaining = list, acc = z)
}