В стандартной библиотеке Scala методы коллекций (map, flatMap, scan и другие) принимают экземпляр типа CanBuildFrom в качестве неявного параметра. В этой статье мы подробно разберём, для чего нужен этот трейт, как он работает и чем может быть полезен разработчику.
Как это работает
Основная цель, которой служит CanBuildFrom — предоставление компилятору типа результата для методов map, flatMap и им подобных, о чём подсказывает, например, определение map в трейте TraversableLike:
def map[B, That](f: A => B)(implicit bf: CanBuildFrom[Repr, B, That]): That
Метод возвращает объект типа That, который фигурирует в описании только в качестве параметра CanBuildFrom. Подходящий экземпляр CanBuildFrom выбирается компилятором на основании типа исходной коллекции Repr и типа результата пользовательской функции B. Выбор производится из набора значений, объявленных в объекте Predef и компаньонах коллекций (правила выбора неявных значений заслуживают отдельной статьи и подробно описаны в спецификации языка).
По сути, при использовании CanBuildFrom происходит такой же вывод типа результата, как и в случае простейшего параметризованного метода:
scala> def f[T](x: List[T]): T = x.head
f: [T](x: List[T])T
scala> f(List(3))
res0: Int = 3
scala> f(List(3.14))
res1: Double = 3.14
scala> f(List("Pi"))
res2: String = Pi
То есть, при вызове
List(1, 2, 3).map(_ * 2)
компилятор выберет экземпляр CanBuildFrom из класса GenTraversableFactory, который описан следующим образом:
class GenericCanBuildFrom[A] extends CanBuildFrom[CC[_], A, CC[A]]
и вернёт коллекцию того же типа но с элементами, полученными от пользовательской функции: CC[A]. В других случаях компилятор может подобрать более подходящий тип результата, например, для строк:
scala> "abc".map(_.toUpper) // Predef.StringCanBuildFrom
res3: String = ABC
scala> "abc".map(_ + "*") // Predef.fallbackStringCanBuildFrom[String]
res4: scala.collection.immutable.IndexedSeq[String] = Vector(a*, b*, c*)
scala> "abc".map(_.toInt) // Predef.fallbackStringCanBuildFrom[Int]
res5: scala.collection.immutable.IndexedSeq[Int] = Vector(97, 98, 99)
В первом случае выбран StringCanBuildFrom, результат — String:
implicit val StringCanBuildFrom: CanBuildFrom[String, Char, String]
Во втором и третьем — метод fallbackStringCanBuildFrom, результат — IndexedSeq:
implicit def fallbackStringCanBuildFrom[T]: CanBuildFrom[String, T, immutable.IndexedSeq[T]]
Использование breakOut
Рассмотрим использование класса Map. Коллекцию такого типа легко преобразовать в Iterable, если вернуть из функции преобразования не пару, а единственное значение:
scala> Map(1 -> "a", 2 -> "b", 3 -> "c").map(_._2)
res6: scala.collection.immutable.Iterable[String] = List(a, b, c)
Но чтобы получить Map из списка пар нужно вызвать метод toMap:
scala> List('a', 'b', 'c').map(x => x.toInt -> x)
res7: List[(Int, Char)] = List((97,a), (98,b), (99,c))
scala> List('a', 'b', 'c').map(x => x.toInt -> x).toMap
res8: scala.collection.immutable.Map[Int,Char] = Map(97 -> a, 98 -> b, 99 -> c)
Либо воспользоваться методом breakOut вместо неявного параметра:
scala> import collection.breakOut
import collection.breakOut
scala> List('a', 'b', 'c').map(x => x.toInt -> x)(breakOut)
res9: scala.collection.immutable.IndexedSeq[(Int, Char)] = Vector((97,a), (98,b), (99,c))
Метод, как следует из названия, позволяет "вырваться" из границ типа исходной коллекции и предоставить компилятору больше свободы в выборе экземпляра CanBuildFrom:
def breakOut[From, T, To](implicit b: CanBuildFrom[Nothing, T, To]): CanBuildFrom[From, T, To]
Из описания видно, что breakOut не специализирует ни один из трёх параметров, а значит, может быть применён вместо любого экземпляра CanBuildFrom. Сам breakOut неявно принимает объект типа CanBuildFrom, но параметр From в данном случае заменён на Nothing, что позволяет компилятору использовать любой доступный экземпляр CanBuildFrom (так происходит потому что параметр From объявлен как контравариантный, а тип Nothing является потомком любого типа.)
Другими словами, breakOut предоставляет дополнительную "прослойку", которая позволяет компилятору выбирать из всех доступных реализаций CanBuildFrom, а не только из тех, которые допустимы для типа исходной коллекции. В примере выше это даёт возможность использовать CanBuildFrom из компаньона Map, несмотря на то, что изначально мы работали с List. Ещё один пример — получение строки из списка символов:
scala> List('a', 'b', 'c').map(_.toUpper)
res10: List[Char] = List(A, B, C)
scala> List('a', 'b', 'c').map(_.toUpper)(breakOut)
res11: String = ABC
Реализация CanBuildFrom[String, Char, String] объявлена в Predef и потому имеет приоритет над объявлениями в компаньонах коллекций.
Пример использования со списком Future
В качестве небольшого примера использования CanBuildFrom напишем реализацию, которая будет автоматически собирать список Future в один объект, как это делает Future.sequence:
List[Future[T]] -> Future[List[T]]
Для начала заглянем внутрь CanBuildFrom. Трейт объявляет два абстрактных метода apply, которые возвращают построитель новой коллекции на основе результатов пользовательской функции:
def apply(): Builder[Elem, To]
def apply(from: From): Builder[Elem, To]
Следовательно, чтобы предоставить собственную реализацию CanBuildFrom, нужно подготовить и Builder, в котором реализовать методы добавления элемента, очистки буфера и получения результата:
class FutureBuilder[A] extends Builder[Future[A], Future[Iterable[A]]] {
private val buff = ListBuffer[Future[A]]()
def +=(elem: Future[A]) = { buff += elem; this }
def clear = buff.clear
def result = Future.sequence(buff.toSeq)
}
Сама реализация CanBuildFrom тривиальна:
class FutureCanBuildFrom[A] extends CanBuildFrom[Any, Future[A], Future[Iterable[A]]] {
def apply = new FutureBuilder[A]
def apply(from: Any) = apply
}
implicit def futureCanBuildFrom[A] = new FutureCanBuildFrom[A]
Проверяем:
scala> Range(0, 10).map(x => Future(x * x))
res12: scala.concurrent.Future[Iterable[Int]] = scala.concurrent.impl.Promise$DefaultPromise@360e2cfb
Всё работает! Благодаря методу futureCanBuildFrom мы получили непосредственно Future[Iterable[Int]], т.е. преобразование промежуточной коллекции было выполнено автоматически.
Внимание: это просто пример использования CanBuildFrom, я не утверждаю, что такое решение нужно использовать в вашем боевом коде или что оно чем-либо лучше обычного оборачивания в Future.sequence. Будьте внимательны и не копируйте код в ваш проект без предварительного анализа последствий!
Заключение
Использование CanBuildFrom тесно связано с неявными параметрами, поэтому чёткое понимание логики выбора значений убережёт вас от потери времени при отладке — не поленитесь заглянуть в спецификацию языка или Scala FAQ. Компилятор также может помочь и показать, какие неявные значения были выбраны, если собрать программу с флагом -Xprint:typer — это здорово экономит время.
CanBuildFrom — весьма специфичная штука и вам, скорее всего, не придётся тесно работать с ним, если только вы не разрабатываете новые структуры данных. Тем не менее, понимание принципов его работы будет не лишним и позволит лучше разобраться во внутреннем устройстве стандартной библиотеки.
На этом всё, спасибо и успехов в изучении Scala!
Исправления и дополнения к статье, как всегда, приветствуются.
DDesideria
Спасибо за статью.
Забавно, что хотя CanBuildFrom и незаменима в некоторых случаях, однако есть план в будущем попробовать избавиться от этой функции. Подробнее здесь
denis-it
Спасибо за ссылку! Похоже, это будет значительное упрощение за счёт разумных ограничений.
NaHCO3
Причём здесь разумные ограничения? Скорее отказ от старых концепций скалируемого дизайна приложений.
Старые классы коллекций олицетворяют идиоматический подход скалы. Множество мелких трейтов показывают принципы декомпозиции в условиях мультинаследования, библиотека коллекций иллюстрирует зачем вообще нужны трейты и какие преимущества от них можно получить.
Сложная параметризация типов методов показывает принципы ко-контр-вариантности и показывают пример типобезопасного программирования. Не как это принято в джаве — в любой непонятной ситуации передавай Object и используй динамический каст, а как это принято в скале — напиши два десятка лишних символов, но обеспечь корректный вывод типов.
CanBuildFrom — идеальный пример использования имплиситов. Он уместный, потому что без него задача сохранения типов при операциях не разрешима для генериков. В остальном библиотека демонстрирует умеренность и избегает неоправданного применения имплиситов. Это прям так как задумано в скале, и совсем не похоже на то, что делают из скалы хаскаляторщики, которые пихают имплиситы в каждую дырку, и даже заменяют ими наследование, хотя для JVM языка гораздо естественнее использовать наследование, встроенное в платформу, чем опирающиеся на косный язык имплиситов, которые не возможно удобно использовать без кодогенерации на уровне макропарадиза.
Отказ от этой библиотеки коллекций — это фактические признание того, что идеи, стоящие за старой скалой, были ошибочными, их требуется переработать, разработать новый идеоматический способ кодирования под скалу. И если рассматривать то предложение, на которое ссылается DDesidera, то этот способ чертовски похож на джаву. Просто с небольшим количеством сахара.
Но ведь у нас уже есть одна джава. Есть ломбок для её сахаризации. Бессмысленно тягаться с джавой на её поле, и может закончиться печально для скалы.