[Из песочницы] Тонкости Scala: изучаем CanBuildFrom10.04.2017 19:34

В стандартной библиотеке 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]]

Рассмотрим использование класса 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 и потому имеет приоритет над объявлениями в компаньонах коллекций.

В качестве небольшого примера использования 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!

Исправления и дополнения к статье, как всегда, приветствуются.

Комментарии (0)