Folding a list of tuples using Scala

Question

What's wrong with this simple scala code?

val l = List(("a", 1), ("b", 2), ("c", 3), ("d", 4), ("e", 5))
l.fold(0) {(acc: Int, tup: (String, Int)) => acc + tup._2}

:9: error: type mismatch; found : (Int, (String, Int)) => Int required: (Any, Any) => Any l.fold(0) {(acc: Int, tup: (String, Int)) => acc + tup._2}

In other functional languages (e.g., f#) this works:

let l = [("a", 1); ("b", 2); ("c", 3); ("d", 4)];;
List.fold(fun accm tup -> accm + (snd tup)) 0 l;;
val it : int = 10

Answer 1

The fold method assumes an associative operator and can in theory (e.g. when using parallelism) be performed in arbitrary order. The signature thus makes it clear that the accumulating type must be a super-type of the collection's element:

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

The inferred super-type of (String, Int) and Int is Any.

This is all described in the API documentation.

---

What you want is a foldLeft or foldRight which do not have this restriction on the type:

def foldLeft[B](z: B)(f: (B, A) ⇒ B): B 

Therefore:

l.foldLeft(0) { (acc, tup) => acc + tup._2 }

or

(0 /: l) { case (acc, (_, n)) => acc + n }