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

Question

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

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

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?

Answer 1

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).

Answer 2

You're right. Let's recall definitions of foldLeft and foldRight

@tailrec
def foldLeft[A, B](init: A)(f: (A, B) => A)(bs: List[B]): A = bs match {
  case Nil      => init
  case b :: bs1 => foldLeft(f(init, b))(f)(bs1)
}

def foldRight[A, B](init: A)(f: (B, A) => A)(bs: List[B]): A = bs match {
  case Nil      => init
  case b :: bs1 => f(b, foldRight(init)(f)(bs1))
}

foldLeft is tail-recursive while foldRight corresponds to ordinary structural recursion over a list.

So tail-recursive definition of sum (with a helper function and accumulator)

def sum(xs: List[Int]): Int = {
  @tailrec
  def loop(xs1: List[Int], acc: Int): Int = xs1 match {
    case Nil     => acc
    case y :: ys => loop(ys, acc + y)
  }

  loop(xs, 0)
}

aka

def sum(xs: List[Int]): Int = {
  def loop(xs1: List[Int]): Int => Int = xs1 match {
    case Nil     => acc => acc
    case y :: ys => acc => loop(ys)(acc + y)
  }

  loop(xs)(0)
}

can be expressed via foldLeft

def sum(xs: List[Int]): Int = {
  def loop(xs1: List[Int], acc: Int): Int =
    foldLeft[Int => Int, Int](acc1 => acc1)(
      (tailRes, y) => acc1 => tailRes(acc1 + y)
    )(xs1)(acc)

  loop(xs, 0)
}

aka

def sum(xs: List[Int]): Int =
  foldLeft[Int => Int, Int](identity)(
    (tailRes, y) => acc => tailRes(acc + y)
  )(xs)(0)

But ordinary structural-recursive definition of sum

def sum(xs: List[Int]): Int = xs match {
  case Nil     => 0
  case y :: ys => y + sum(ys)
}

can be expressed via foldRight

def sum(xs: List[Int]): Int = foldRight[Int, Int](0)(_ + _)(xs)

What does e:B, f:(B,A)=>B) : B

Actually, in Scala standard library foldLeft and foldRight are defined via iteration rather than recursion

override def foldLeft[B](z: B)(op: (B, A) => B): B = {
  var acc = z
  var these: LinearSeq[A] = coll
  while (!these.isEmpty) {
    acc = op(acc, these.head)
    these = these.tail
  }
  acc
}

final override def foldRight[B](z: B)(op: (A, B) => B): B = {
  var acc = z
  var these: List[A] = reverse
  while (!these.isEmpty) {
    acc = op(these.head, acc)
    these = these.tail
  }
  acc
}

By the way, since foldRight can define arbitrary structural recursion over a list, foldLeft can be expressed via foldRight (the type A => A is chosen because foldLeft is recursively expressed via foldLeft for a different init, so we need being able to modify init)

def foldLeft[A, B](init: A)(f: (A, B) => A)(bs: List[B]): A =
  foldRight[A => A, B](init1 => init1)(
    (b, tailRes) => init1 => tailRes(f(init1, b))
  )(bs)(init)

Similarly, foldRight can be expressed via foldLeft (in by-default eager Scala but not in by-default lazy Haskell, because in Haskell foldRight works even for infinite lists, streams in Scala, but foldLeft works only for finite lists)

def foldRight[A, B](init: A)(f: (B, A) => A)(bs: List[B]): A =
  foldLeft[A => A, B](init1 => init1)(
    (tailRes, b) => init1 => tailRes(f(b, init1))
  )(bs)(init)