Understanding foldLeft with Map instead of List

Question

I fould like to understand how foldLeft works for Maps. I do understand how it works if I have a List and call on it foldLeft with a zero-element and a function:

val list1 = List(1,2,3)
list1.foldLeft(0)((a,b) => a + b)

Where I add the zero-element 0 with the first element of list1 and then add the second element of list1 and so on. So output becomes the new input and the first input is the zero-element.

Now I got the code

val map1 = Map(1 -> 2.0, 3 -> 4.0, 5 -> 6.2) withDefaultValue 0.0
val map2 = Map(0 -> 3.0, 3 -> 7.0) withDefaultValue 0.0
def myfct(terms: Map[Int, Double], term: (Int, Double)): Map[Int, Double] = ???

map1.foldLeft(map2)(myfct)

1. So my first element here is a Tuple2, but since map2 is a Map and not a Tuple2, what is the zero-element?
2. When we had a List, namely list1, we always "took the next element in list1". What is the "next element in map1? Is it another pair of map1?

Answer 1

In this context, you can think of a Map as a list of tuples. You can create a list like this: List(1 -> 2.0, 3 -> 4.0, 5 -> 6.2), and call foldLeft on it (that is more or less exactly what Map.foldLeft does). If you understand how foldLeft works with lists, then now you know how it works with Maps too :) To answer your specific questions:

1. The first parameter of foldLeft can be of any type. You could pass in a Map instead of an Int in your first example too. It does not have to be of the same type as elements of the collection you are processing (although, it could be), as you have in your first example, nor does it need to be the same type as the collection itself, as you have it in the last example. Consider this for the sake of example:

    List(1,2,3,4,5,6).foldLeft(Map.empty[String,Int]) { case(map,elem) => 
      map + (elem.toString -> elem) 
    }
   

This produces the same result as list.map { x => x.toString -> x }.toMap. As you can see, the first parameter here is a Map, that is neither List nor an Int.

The type you pass to foldLeft is also the type it returns, and the type that the function you pass in returns. It is not "element zero". foldLeft will pass that parameter to your reducer function, along with the first element of the list. Your function will combine the two elements, and produce a new value of the same type as the first param. That value is passed in again, again with the second element ... etc. Perhaps, inspecting the signature of foldLeft would be helpful:

   foldLeft[B](z: B)(op: (B, A) ⇒ B): B

Here A is the type of your collection elements, and B can be anything, the only requirement is that the four places where it appears have the same type.

Here is another example, that is (almost) equivalent to list.mkString(","):

   List(1,2,3,4,5,6).foldLeft("") { 
     case("", i) => i.toString
     case(s,i) => s + "," + i
   }

2. As I explained in the beginning, a map in this context is a kind of a list (a sequence rather). Just like "we always took the next element of the list" when we dealt with lists, we will take the "next element of the map" in this case. You said it yourself, the elements of the map are tuples, so that's what the type of the next element will be:

    Map("one" -> 1, "two" -> 2, "three" -> 3)
     .foldLeft("") { 
       case("", (key,value)) => key + "->" + value
       case(s, (key,value)) => s + ", " + key + "->" + value
     }
   

Answer 2

As mentioned above, the signature of the foldLeft operation is as shown:

foldLeft[B](z: B)(op: (B, A) ⇒ B): B

The resulting type of the operation is B. So, this answers your first question:

So my first element here is a Tuple2, but since map2 is a Map and not a Tuple2, what is the zero-element?

The zero-element is whatever you want to output from the foldLeft. It could be an Int or a Map or anything else for that matter.

op in the function signature (i.e the second argument), is how you would like to operate on that for each element of map1, which is a (key,value) pair, or another way of writing it is as key -> value.

Let's try and understand it by building it up with more simpler operations.

val map1 = Map(1 -> 1.0, 4 -> 4.0, 5 -> 5.0) withDefaultValue 0.0
val map2 = Map(0 -> 0.0, 3 -> 3.0) withDefaultValue 0.0

// Here we're just making the output an Int
// So we just add the first element of the key-value pair.
def myOpInt(z: Int, term: (Int, Double)): Int = {
  z + term._1
}

// adds all the first elements of the key-value pairs of map1 together
map1.foldLeft(0)(myOpInt)  // ... output is 10
// same as above, but for map2 ...
map2.foldLeft(0)(myOpInt) // ... output is 3

Now, taking it to the next step by using a zero element (z) as an existing map...we would essentially add elements to that map we are using as z.

val map1 = Map(1 -> 1.0, 4 -> 4.0, 5 -> 5.0) withDefaultValue 0.0
val map2 = Map(0 -> 0.0, 3 -> 3.0) withDefaultValue 0.0

// Here z is a Map of Int -> Double
// We expect a pair of (Int, Double) as the terms to fold left with z
def myfct(z: Map[Int, Double], term: (Int, Double)): Map[Int, Double] = {
  z + term
}

map1.foldLeft(map2)(myfct) 
// output is Map(0 -> 0.0, 5 -> 5.0, 1 -> 1.0, 3 -> 3.0, 4 -> 4.0)
// i.e. same elements of both maps concatenated together, albeit out of order, since Maps don't guarantee order ...

When we had a List, namely list1, we always "took the next element in list1". What is the "next element in map1? Is it another pair of map1?

Yes, it's another key-value pair (k,v) in map1.