Scala – Fold and foldLeft method difference

scala

I am not sure what is the difference between fold and foldLeft in Scala.

The question Difference between fold and foldLeft or foldRight? has an answer that talks about ordering. That is understandable. But I still don't understand why this works (from REPL):

scala> Array("1","2","3").foldLeft(0)(_ + _.toInt)
res6: Int = 6

but this does not:

scala> Array("1","2","3").fold(0)(_ + _.toInt)
<console>:8: error: value toInt is not a member of Any
              Array("1","2","3").fold(0)(_ + _.toInt)
                                               ^

What does this error message mean?

This line from the documentation is also confusing to me.

z – a neutral element for the fold operation; may be added to the
result an arbitrary number of times, and must not change the result
(e.g., Nil for list concatenation, 0 for addition, or 1 for
multiplication.)

Why will it be added an arbitrary number of times? I thought folding works differently.

Best Answer

As defined by Scala, foldLeft is a linear operation while fold is allowed to be a tree operation. For example:

List(1,2,3,4,5).foldLeft(0)(_ + _)
// This is the only valid order of operations
0+1 = 1
      1+2 = 3
            3+3 = 6
                  6+4 = 10
                        10 + 5 = 15
                                 15  // done

List(1,2,3,4,5).fold(0)(_ + _)
// This is valid
0+1 = 1             0+3 = 3           0+5 = 5
      1+2 = 3             3+4 = 7           5
            3         +         7=10        5
                                  10    +   5 = 15
                                                15  // done

In order to allow arbitrary tree decompositions of a sequential list, you must have a zero that doesn't do anything (so you can add it wherever you need it in the tree) and you must create the same sort of thing that you take as your binary arguments so the types don't change on you depending on how you decompose the tree.

(Being able to evaluate as a tree is nice for parallelization. If you want to be able to transform your output time as you go, you need both a combination operator and a standard start-value-transforms-sequence-element-to-desired-type function just like foldLeft has. Scala has this and calls it aggregate, but in some ways this is more like foldLeft than fold is.)

tl;dr

class C defines a class, just as in Java or C++.
object O creates a singleton object O as instance of some anonymous class; it can be used to hold static members that are not associated with instances of some class.
object O extends T makes the object O an instance of trait T; you can then pass O anywhere, a T is expected.
if there is a class C, then object C is the companion object of class C; note that the companion object is not automatically an instance of C.

Also see Scala documentation for object and class.

`object` as host of static members

Most often, you need an object to hold methods and values/variables that shall be available without having to first instantiate an instance of some class. This use is closely related to static members in Java.

object A {
  def twice(i: Int): Int = 2*i
}

You can then call above method using A.twice(2).

If twice were a member of some class A, then you would need to make an instance first:

class A() {
  def twice(i: Int): Int = 2 * i
}

val a = new A()
a.twice(2)

You can see how redundant this is, as twice does not require any instance-specific data.

`object` as a special named instance

You can also use the object itself as some special instance of a class or trait. When you do this, your object needs to extend some trait in order to become an instance of a subclass of it.

Consider the following code:

object A extends B with C {
  ...
}

This declaration first declares an anonymous (inaccessible) class that extends both B and C, and instantiates a single instance of this class named A.

This means A can be passed to functions expecting objects of type B or C, or B with C.

Additional Features of `object`

There also exist some special features of objects in Scala. I recommend to read the official documentation.

def apply(...) enables the usual method name-less syntax of A(...)
def unapply(...) allows to create custom pattern matching extractors
if accompanying a class of the same name, the object assumes a special role when resolving implicit parameters

Scala – the difference between Scala’s case class and class

Case classes can be seen as plain and immutable data-holding objects that should exclusively depend on their constructor arguments.

This functional concept allows us to

use a compact initialization syntax (Node(1, Leaf(2), None)))
decompose them using pattern matching
have equality comparisons implicitly defined

In combination with inheritance, case classes are used to mimic algebraic datatypes.

If an object performs stateful computations on the inside or exhibits other kinds of complex behaviour, it should be an ordinary class.

Best Answer

Related Solutions

Scala – Difference between object and class in Scala

tl;dr

object as host of static members

object as a special named instance

Additional Features of object

Scala – the difference between Scala’s case class and class

Related Topic

`object` as host of static members

`object` as a special named instance

Additional Features of `object`