Scala : fold vs foldLeft

by

The method fold (originally added for parallel computation) is less powerful than foldLeft in terms of types it can be applied to. Its signature is:

def fold[A1 >: A](z: A1)(op: (A1, A1) => A1): A1

This means that the type over which the folding is done has to be a supertype of the collection element type.

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

The reason is that fold can be implemented in parallel, while foldLeft cannot. This is not only because of the *Left part which implies that foldLeft goes from left to right sequentially, but also because the operator op cannot combine results computed in parallel — it only defines how to combine the aggregation type B with the element type A, but not how to combine two aggregations of type B. The fold method, in turn, does define this, because the aggregation type A1 has to be a supertype of the element type A, that is A1 >: A. This supertype relationship allows in the same time folding over the aggregation and elements, and combining aggregations — both with a single operator.

But, this supertype relationship between the aggregation and the element type also means that the aggregation type A1 in your example should be the supertype of (ArrayBuffer[Int], Int). Since the zero element of your aggregation is ArrayBuffer(1, 2, 4, 5) of the type ArrayBuffer[Int], the aggregation type is inferred to be the supertype of both of these — and that’s Serializable with Equals, the only least upper bound of a tuple and an array buffer.

In general, if you want to allow parallel folding for arbitrary types (which is done out of order) you have to use the method aggregate which requires defining how two aggregations are combined. In your case:

r.aggregate(ArrayBuffer(1, 2, 4, 5))({ (x, y) => x -- y._1 }, (x, y) => x intersect y)

Btw, try writing your example with reduce/reduceLeft — because of the supertype relationship between the element type and the aggregation type that both these methods have, you will find that it leads to a similar error as the one you’ve described.

More Related Contents:

  1. Difference between reduce and foldLeft/fold in functional programming (particularly Scala and Scala APIs)?
  2. Reduce, fold or scan (Left/Right)?
  3. Functional programming, Scala map and fold left [closed]
  4. Difference between fold and foldLeft or foldRight?
  5. Is the Scala 2.8 collections library a case of “the longest suicide note in history”? [closed]
  6. What are type lambdas in Scala and what are their benefits?
  7. How do I break out of a loop in Scala?
  8. What is the purpose of type ascriptions in Scala?
  9. Provide schema while reading csv file as a dataframe
  10. Scala: Why mapValues produces a view and is there any stable alternatives?
  11. Joining Spark dataframes on the key
  12. How to set heap size for sbt?
  13. Scala Map implementation keeping entries in insertion order?
  14. Modify collection inside a Spark RDD foreach
  15. How to write unit tests in Spark 2.0+?
  16. Easy idiomatic way to define Ordering for a simple case class
  17. What is *so* wrong with case class inheritance?
  18. Is there a reason not to use SparkContext.getOrCreate when writing a spark job?
  19. What are the various join types in Spark?
  20. Accessing value returned by scala futures
  21. Static return type of Scala macros
  22. Spark Scala list folders in directory
  23. Exception in thread “main” java.lang.NoSuchMethodError: scala.Product.$init$(Lscala/Product;)
  24. How to remove parentheses around records when saveAsTextFile on RDD[(String, Int)]?
  25. Why is this implicit ambiguity behaviour happening?
  26. forall in Scala
  27. Treating an SQL ResultSet like a Scala Stream
  28. Scala asInstanceOf with parameterized types
  29. How do I run an sbt main class from the shell as normal command-line program?
  30. Akka-Stream implementation slower than single threaded implementation

Leave a Comment