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

Question

I am confused about what this means. I understand currying but I can't seem to read the code altogether.

def foldLeft [A,B](xs:List[A], e:B, f:(B,A)=>B): B

Answer 1

Just a couple of advices.

By the way, there is no currying in

def foldLeft[A,B](xs: List[A], e: B, f: (B, A) => B): B

Currying would be if you had f: B => A => B or def foldLeft[A, B](xs: List[A])(e: B)(f: (B, A) => B): B or def foldLeft[A, B]: List[A] => B => ((B, A) => B) => B etc. Now foldLeft is just a higher-order function (method), i.e. a function accepting another function (f).

• You can read wiki article about foldRight/foldLeft:

https://en.wikipedia.org/wiki/Fold_(higher-order_function)

Especially look at the pictures how we deconstruct a list and starting from what end we perform our calculations:

• You can think of foldRight/foldLeft as a just short way to define a recursion (instead of pattern matching a list and making recursive calls).

Let's consider an example. Let's have some recursion. For example let's have a wrapper class

case class Value[A](value: A)

And let's transform a list of Value[A] into a value wrapping a list of A i.e. List[Value[A]] into Value[List[A]]. For example we'd like to transform List(Value(1), Value(2), Value(3)) into Value(List(1, 2, 3)) (I actually needed such function recently). Surely, we could do this with .map but let's pretend that we don't know map (it shouldn't be surprising that we can do mapping because map can be expressed via foldRight/foldLeft).

We can do this recursively in two ways (at least). Either simple recursion

def valuesToValue[A](values: List[Value[A]]): Value[List[A]] = values match {
  case Nil     => Value(Nil)
  case v :: vs => Value(v.value :: valuesToValue(vs).value)
}

or tail recursion with a helper function and accumulator

def valuesToValue[A](values: List[Value[A]]): Value[List[A]] = {
  @tailrec
  def loop(values: List[Value[A]], acc: Value[List[A]]): Value[List[A]] = values match {
    case Nil     => Value(acc.value.reverse)
    case v :: vs => loop(vs, Value(v.value :: acc.value))
  }

  loop(values, Value(Nil))
}

Very simple. Just wrapping-unwrapping.

Both recursive implementations of valuesToValue can be (automatically) re-written with foldRight/foldLeft. The former recursion can be re-written with foldRight. The latter recursion (tail one) can be re-written with foldLeft.

Let's re-write the 1st recursion with foldRight. The value from branch case Nil => ... becomes the 1st argument of foldRight. The value from branch case v :: vs => ... becomes the 2nd argument of foldRight if we replace the result of recursive call valuesToValue(vs) with a new variable res, so in the 2nd argument of foldRight we'll have a function of v: Value[A] and res: Value[List[A]]

def valuesToValue[A](values: List[Value[A]]): Value[List[A]] =
  values.foldRight( Value(Nil: List[A]) ){
    (v, res) => Value(v.value :: res.value)
  }

Let's re-write the 2nd recursion (tail one) with foldLeft.

First of all, let's recall that because of currying we can understand the helper loop as a single-parameter function into Value[List[A]] => Value[List[A]]

def loop(values: List[Value[A]]): Value[List[A]] => Value[List[A]] = values match {
  case Nil     => acc => Value(acc.value.reverse)
  case v :: vs => acc => loop(vs)(Value(v.value :: acc.value))
}

Now the value from branch case Nil => ... becomes the 1st argument of foldLeft. The value from branch case v :: vs => ... becomes the 2nd argument of foldLeft if we replace the result of recursive call loop(vs)(_) with a new variable res (a function)

def valuesToValue[A](values: List[Value[A]]): Value[List[A]] = {
  def loop(values: List[Value[A]]): Value[List[A]] => Value[List[A]] =
    values.foldRight[Value[List[A]] => Value[List[A]]](
                  acc => Value(acc.value.reverse)
    )(
      (v, res) => acc => res(Value(v.value :: acc.value))
    )

  loop(values)(Value(Nil))
}

So, roughly speaking, values from branches case Nil => ... and case v :: vs => ... become arguments of foldRight/foldLeft depending on whether we calculate with simple recursion or tail recursion with accumulator.

Answer 2

Let's dive into this method signature:

foldLeft[A,B](xs: List[A], e: B, f: (B, A) => B): B

• foldLeft is a method with 3 parameters
• A and B are type parameters
• xs is 1st parameter of the method, of type List[A]
• e is 2nd parameter, of type B
• f is 3rd parameter, of type (B, A) => B
  • the type (B, A) => B represents a function taking two parameters of type B and A respectively, and returning a B
• finally, B is the return type of the method