Понимание foldLeft с картой вместо списка

Я хотел бы понять, как foldLeft работает с Картами. Я понимаю, как это работает, если у меня есть список и я вызываю его foldLeft с нулевым элементом и функцией:

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

Где я добавляю нулевой элемент 0 к первому элементу list1, а затем добавляю второй элемент list1 и так далее. Таким образом, выход становится новым входом, а первый вход — нулевым элементом.

Теперь я получил код

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. Итак, мой первый элемент здесь — Tuple2, но поскольку map2 — это Map, а не Tuple2, что такое нулевой элемент?
  2. Когда у нас было List, а именно list1, мы всегда "брали следующий элемент в list1". Что такое «следующий элемент в map1? Это еще одна пара map1?

dictionary scala language-concepts foldleft
person Make42    schedule 06.05.2016    source источник

Ответы (1)


arrow_upward
7
arrow_downward

В этом контексте вы можете думать о Map как о списке кортежей. Вы можете создать такой список: List(1 -> 2.0, 3 -> 4.0, 5 -> 6.2) и вызвать для него foldLeft (это более или менее точно то, что делает Map.foldLeft). Если вы понимаете, как foldLeft работает со списками, то теперь вы знаете, как это работает и с Картами :) Чтобы ответить на ваши конкретные вопросы:

  1. Первый параметр foldLeft может быть любого типа. Вы также можете передать карту вместо int в своем первом примере. Он не обязательно должен быть того же типа, что и элементы обрабатываемой вами коллекции (хотя и может быть), как в первом примере, и не обязательно должен быть того же типа, что и сама коллекция, как вы есть в последнем примере. Рассмотрим это для примера:

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

Это дает тот же результат, что и list.map { x => x.toString -> x }.toMap. Как видите, первый параметр здесь — Map, а не List и не Int.

Тип, который вы передаете foldLeft, также является типом, который он возвращает, и типом, который возвращает функция, которую вы передаете. Это не «нулевой элемент». foldLeft передаст этот параметр вашей функции редуктора вместе с первым элементом списка. Ваша функция объединит два элемента и создаст новое значение того же типа, что и первый параметр. Это значение передается снова, снова со вторым элементом... и т. д. Возможно, будет полезно проверить подпись foldLeft:

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

Здесь A — это тип элементов вашей коллекции, а B может быть любым, единственное требование — чтобы четыре места, где он появляется, имели один и тот же тип.

Вот еще один пример, который (почти) эквивалентен list.mkString(","):

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

  1. Как я объяснил в начале, карта в этом контексте — это своего рода список (скорее, последовательность). Точно так же, как «мы всегда брали следующий элемент списка», когда имели дело со списками, в данном случае мы будем брать «следующий элемент карты». Вы сами сказали, что элементы карты — это кортежи, поэтому тип следующего элемента будет таким:

    Map("one" -> 1, "two" -> 2, "three" -> 3)
 .foldLeft("") { 
   case("", (key,value)) => key + "->" + value
   case(s, (key,value)) => s + ", " + key + "->" + value
 }
person Dima    schedule 06.05.2016
comment
1) Спасибо за отличный пост! 2) как у вас в последнем примере. мне кажется неправильным: здесь A - это Tuple2, а не Map. Пожалуйста, исправьте или прокомментируйте. 3) Почему case(map,elem), а не просто (map,elem) в первом примере? 4) Ни scala.collection.immutable.Map, ни scala.collection.immutable.Iterable не реализуют foldLeft. Почему во всей этой коллекции есть foldLeft? - person Make42; 06.05.2016
comment
Я думаю, что 4) неверно, однако я все еще немного смущен из-за всех этих разных реализаций... - person Make42; 06.05.2016
comment
Из docs.scala-lang.org/tutorials/FAQ/collections кажется для меня карты не списки. Реализованы ли они внутри как списки кортежей? Это то, что предлагает ваш пост, но правда ли это? (Я не знаю, как проверить исходный код Map.) - person Make42; 06.05.2016
comment
Если вы посмотрите на документ Scala, вы увидите (например) для foldLeft в классах определения карты TraversableOnce → GenTraversableOnce, сообщающих вам, где он определен (scala- lang.org/api/2.11.8/). Также вверху scaladoc класса находится ссылка на источник. Опять же, для карты это github.com/scala/scala/blob/v2.11.8/src/library/scala/ - person The Archetypal Paul; 06.05.2016
comment
И нет, они не реализованы как Lists из Tuples, но есть способы доступа к контенту как Tuples. Именно это и делает foldLeft (через foreach, который использует iterator (scala-lang.org/api/2.11.8/), который, как говорится на этой странице, должен быть реализован конкретными подклассами Map. .. - person The Archetypal Paul; 06.05.2016
comment
@ Make42 Make42, вы правы, Карты - это не списки, и они также не реализованы как списки. Все, что я сказал, это то, что в этом контексте вы можете смотреть карту как если бы она была списком кортежей. Причина, по которой вы можете это сделать, заключается в том, что, хотя карты и не являются списками, у них есть некоторые свойства, такие как, например, возможность сканирования последовательности элементов, что важно в данном случае. - person Dima; 06.05.2016
comment
@Make42, чтобы ответить на ваши вопросы: в вашем последнем примере я имел в виду передачу map2 в foldLeft. A - это кортеж, но B в вашем случае был Map. Ре. case(map,elem) можно заменить только на (map, elem) в этом конкретном случае, вы правы. Я просто привык писать case в этом контексте, потому что это более общий термин. foldLeft реализован в каком-то суперклассе Map, TraversableOnce я думаю... - person Dima; 06.05.2016