List()String means what?

scala> li.fold(Nil)(_.toString + _.toString)
val res26: Any = List()32140

scala> li.fold("")(_.toString + _.toString)
val res27: Any = 32140

The first result List()32140 means what? I am not sure about this.
please help point it out.
Thank you.

And, for this comparison:

scala> li
val res28: List[Int] = List(3, 2, 1, 4, 0)

scala> li.fold("") {_.toString + _.toString}
val res30: Any = 32140

scala> li.map{_.toString}.reduce{_ + _}
val res32: String = 32140

Do you know why the string returned by fold() is type “Any”. But the string returned by map/reduce is type “String” ?

Thanks again.

For this kind of problems, it helps to follow the types.

Let’s check at the signature of foldLeft`

sealed trait List[+A] {
  def fold[B >: A](z: B)(op: (B, A) => B): B
}

Thus, let’s see what the compiler infers when you do this:

(li : List[Int]).fold(Nil : List[Nothing])((acc: B, i: Int) => (acc.toString + i.toString) : String) : B

Thus, it has to infer a type B that is a supertype of Int and of String and of List[Nothing], and Any is the only thing that works for that.

BTW, if you would have used foldLeft for this example: li.fold("") {_.toString + _.toString} you would get back a String as expected.

To be honest, I don’t see any point for fold to exist.

3 Likes

fold exists for parallelizable operations. It requires an associative operator so that the work can be divided up and the partial results combined into a final result.

(On List specifically, of course it’s not going to parallelize anything.)

1 Like

Nil.toString is List(), it isn’t the empty string.

3 Likes

I know this is starting to fall into rant / off-topic territory, but for parallel operations I would rather use aggregate, although I do give the point that having fold as a simple alias to an aggregate were both the seq and comb operations are the same is nice.

However, since the parallel module is already separated from the stdlib and there is no way to abstract over the two, I would guess fold is just a leftover.

1 Like

scala> val li =List(3,2,1,4)
val li: List[Int] = List(3, 2, 1, 4)

scala> li.fold("") {_.toString + _.toString }
val res0: Any = 3214

scala> li.foldLeft("") {_.toString + _.toString }
val res1: String = 3214

scala> li.foldRight("") {_.toString + _.toString }
val res3: String = 3214

@BalmungSan please see the sample code above. my further questions:

  • why foldLeft can return a String type?
  • why foldRight get the same result as foldLeft? I expect it to be 4123.

Thanks in advance.

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)
}
2 Likes

You need a fold to keep your sheep.

1 Like

Quite interesting and then scaladoc clarifies it (why – @ BalmungSan has nicely explained), so we should always fallback to APIdoc when in doubt

List[A]
def foldLeft[B](z: B)(op: (B, A) => B): B
def foldRight[B](z: B)(op: (A, B) => B): B

You are right, but some pointer
List[A].fold[A1 >: A](z: A1)(op: (A1, A1) => A1): A1
is more generalized version of List[A].def reduce[B >: A](op: (B, B) => B): B
It is not really a Foldable structure/pattern, however in List/IterableOnce is implemented by foldLeft(which is true Foldable ), so in that sense, in List, it is redundant , but for others, who knows

Well, as I said to Seth, if the purpose of fold is to allow for parallel computations and the parallel module is no longer part of the stdlib I would say that it is no longer needed. But :man_shrugging:

“why foldRight get the same result as foldLeft? I expect it to be 4123.”

@pengyh if you don’t mind, I’d like to have a go at reinforcing the concepts already explained by @BalmungSan in his great and comprehensive answer

A very simple way to define a left fold is to say that it is a loop. A very simple way to define a right fold of a list with function f and unit z, is to say that it does constructor replacement, i.e. it replaces the empty list with z and the :: function with f

The above is a programmatic definition of left and right folds. In that implementation, the left fold is tail recursive, whereas the right fold isn’t.

Here is a mathematical definition of left and right folds.

As @BalmungSan said:

// For foldLeft:
((0 + 1) + 2) + 3

// For foldRight:
1 + (2 + (3 + 0))

i.e. in a left fold, the function (e.g. +) is applied by associating to the left, whereas in a right fold, it is applied by associating to the right. The book ‘Programming in Scala’ speaks of a left fold producing a left-leaning tree, and a right fold producing a right-leaning tree (see the left and right leaning trees in the above diagrams).

As @BalmungSan said, when the f is associative (associating to the left produces the same result as associating to the right, e.g. +) and z is a unit for f (e.g. z=0 is a unit for +, i.e. 0 + n = n + 0 = n), then left and right fold produce the same result. But if f is not associative, then the results differ.

The behaviour of left and right folds with an associative operation and the operation’s unit is captured by the first duality theorem of folding:

When a right fold is implemented as a non-tail recursive function, it has the disadvantage that it is not stack-safe, i.e. if the list being processed is sufficiently long then the function will encounter a stack overflow exception. One way to avoid that is to define a right fold in terms of a left fold. This can be done thanks to the third duality theorem of fold:

In Scala, foldRight is stack safe, because it exploits the above duality theorem as it is defined in terms of a left fold:

(Urgh! - it looks like “effectively inlines the call to foldRight” should end with foldLeft.)

Finally, I have a slide for what @BalmungSan said here:

// That is why calling foldRight with Nil and :: gets you back the same list.
// And doing the same with foldLeft reverses it.

I hope you find the above useful.

If you liked any of the above, the slides come from the following:

4 Likes