Difference between fold and foldLeft or foldRight?
Solution 1
You're right about the old version of Scala being a problem. If you look at the scaladoc page for Scala 2.8.1, you'll see no fold defined there (which is consistent with your error message). Apparently, fold
was introduced in Scala 2.9.
Solution 2
Short answer:
foldRight
associates to the right. I.e. elements will be accumulated in right-to-left order:
List(a,b,c).foldRight(z)(f) = f(a, f(b, f(c, z)))
foldLeft
associates to the left. I.e. an accumulator will be initialized and elements will be added to the accumulator in left-to-right order:
List(a,b,c).foldLeft(z)(f) = f(f(f(z, a), b), c)
fold
is associative in that the order in which the elements are added together is not defined. I.e. the arguments to fold
form a monoid.
Solution 3
fold
, contrary to foldRight
and foldLeft
, does not offer any guarantee about the order in which the elements of the collection will be processed. You'll probably want to use fold
, with its more constrained signature, with parallel collections, where the lack of guaranteed processing order helps the parallel collection implements folding in a parallel way. The reason for changing the signature is similar: with the additional constraints, it's easier to make a parallel fold.
Solution 4
For your particular example you would code it the same way you would with foldLeft.
val ns = List(1, 2, 3, 4)
val s0 = ns.foldLeft (0) (_+_) //10
val s1 = ns.fold (0) (_+_) //10
assert(s0 == s1)
Solution 5
Agree with other answers. thought of giving a simple illustrative example:
object MyClass {
def main(args: Array[String]) {
val numbers = List(5, 4, 8, 6, 2)
val a = numbers.fold(0) { (z, i) =>
{
println("fold val1 " + z +" val2 " + i)
z + i
}
}
println(a)
val b = numbers.foldLeft(0) { (z, i) =>
println("foldleft val1 " + z +" val2 " + i)
z + i
}
println(b)
val c = numbers.foldRight(0) { (z, i) =>
println("fold right val1 " + z +" val2 " + i)
z + i
}
println(c)
}
}
Result is self explanatory :
fold val1 0 val2 5
fold val1 5 val2 4
fold val1 9 val2 8
fold val1 17 val2 6
fold val1 23 val2 2
25
foldleft val1 0 val2 5
foldleft val1 5 val2 4
foldleft val1 9 val2 8
foldleft val1 17 val2 6
foldleft val1 23 val2 2
25
fold right val1 2 val2 0
fold right val1 6 val2 2
fold right val1 8 val2 8
fold right val1 4 val2 16
fold right val1 5 val2 20
25
Andriy Drozdyuk
I like AI and in particular Reinforcement Learning. I used to like Erlang, Scala, python, Akka and Zeromq! Did my undergrad in Computer Science at University of Toronto. Did my masters in Data Mining at University of New Brunswick. Working as a programmer at NRC and doing PhD part time at Carleton University.
Updated on February 07, 2020Comments
-
Andriy Drozdyuk over 4 years
NOTE: I am on Scala 2.8—can that be a problem?
Why can't I use the
fold
function the same way asfoldLeft
orfoldRight
?In the Set scaladoc it says that:
The result of folding may only be a supertype of this parallel collection's type parameter
T
.But I see no type parameter
T
in the function signature:def fold [A1 >: A] (z: A1)(op: (A1, A1) ⇒ A1): A1
What is the difference between the
foldLeft-Right
andfold
, and how do I use the latter?EDIT: For example how would I write a fold to add all elements in a list? With
foldLeft
it would be:val foo = List(1, 2, 3) foo.foldLeft(0)(_ + _) // now try fold: foo.fold(0)(_ + _) >:7: error: value fold is not a member of List[Int] foo.fold(0)(_ + _) ^
-
Rex Kerr almost 13 years
foldLeft
andfoldRight
are also non-commutative (hence the names) whilefold
may or may not be; I can't help thinking it's a strange choice of naming convention. -
Andriy Drozdyuk almost 13 yearsCould you provide an example of adding all elems in a list? I amended my question!
-
Andriy Drozdyuk almost 13 yearsSorry but I don't understand what monoid is, and also why I can't use fold the same way as foldLeft. See my question for added example.
-
Andriy Drozdyuk almost 13 yearsHm.. I have tried it and it doesn't work. The line with a fold gives me an error (see my question). I am using scala 2.8 - maybe that is a problem?
-
Apocalisp almost 13 yearsA monoid is an associative binary function together with an identity element for that function.
(0)(_+_)
is a monoid, for example.(1)(_*_)
is another example. I think you understand what it is, just not by that name. -
Apocalisp almost 13 yearsRex: Commutativity is not really relevant here.
-
Richard Gomes about 10 yearsMonoids without tears: fsharpforfunandprofit.com/posts/monoids-without-tears