foldRight in terms of foldLeft puzzle

foldRightFoldLeft.md

Task: implement foldLeft function and then foldRight in terms of foldLeft

def foldLeft[A, B](list: List[A], z: B)(op: (B, A) => B): B = {
  def loop(currentList: List[A], acc: B): B = {
    currentList match {
      case Nil          => acc
      case head :: next => loop(next, op(acc, head))
    }
  }
  loop(list, z)
}

def foldRight[A, B](list: List[A], z: B)(op: (A, B) => B): B = {
  foldLeft[A, B => B](list, (b: B) => b)((f, elem) =>(acc: B) => op(elem, f(acc)))(z)
}

Description

In scala (as of version 2.13) foldRight for List is implemented by reversing list at first, and then applying foldLeft function. Solution presented here doesn't do reverse, but it replaces aggregation of a result in some terminal value B with building a function composition, and then applying a value to that composed function

To check the solution we need to try some operation which is not comutative: composition of strings for example("a" + "b" != "b" + "a")

foldLeft("1" :: "2" :: "3" :: Nil, "")(_ + _)  // : String = "123"
foldRight("1" :: "2" :: "3" :: Nil, "")(_ + _) // : String = "321"