scaladictionarylanguage-conceptsfoldleft

Understanding foldLeft with Map instead of List


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?

Solution

  • 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
       }
    
    1. 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
        }