scalafoldfoldleft

reduceLeft (or, foldLeft) vs reduceRight (or, foldRight) in scala


I am learning scala from coursera. In the reduceLeft and reduceRight description this comes along:

enter image description here

and then on the very next slide the teacher says this code pattern is abstracted out as reduceLeft

enter image description here

My questions:

  1. I think the pattern in the first slide is reduceRight and not reduceLeft. Can you please help me understand where I am mistaken? For example: an addition operator on [1,2,3] would lead to (1+sum(2,3)) from the first slide which, I think, is reduceRight. reduceLeft should be (sum(1,2)+3)
  2. I am not able to implement the reduceLeft as reduceRight is implemented raw in the first slide using the case statements? Can you please guide me in the right direction on how to do it?

Solution

  • Re 1.:

    Indeed, as already confirmed in the comments, the pattern in the first slide is reduceRight.

    I think the point of the second slide is to say "that pattern of reducing a list can be abstracted out using a generic method from the standard library" (not "the pattern of the specific solution from the previous slides corresponds to reduceLeft").

    Both reduceLeft and reduceRight would be suitable to implement sum. However: when both reduceLeft/reduceRight (or foldLeft/foldRight) are suitable for a solution, in scala one usually prefers the Left variant (especially when working with Lists) because its implementation is slightly more efficient on Lists. That's most certainly the motivation for focusing on reduceLeft on the second slide.

    Re 2.:

    If you want to implement the sum from the first slide in a left-reducing way, you will need three cases:

    def sum(xs: List[Int]): Int = xs match
      case Nil            => 0
      case x :: Nil       => ???
      case x :: y :: tail => ??? 
    

    I leave it to you to fill out the ???s.

    Note that it will not be possible to implement this left-reducing sum in a tail-recursive manner (unless you introduce an additional helper function with a different signature).