Как коллекции Scala могут возвращать правильный тип коллекции из операции карты?

Question

Примечание. Это часто задаваемый вопрос, который задается специально, поэтому я могу ответить на него сам, так как эта проблема, кажется, возникает довольно часто, и я хочу поместить его в место, где его (можно надеяться) легко найти с помощью поиска.

Как подсказал комментарий к моему ответу здесь

---

Например:

"abcde" map {_.toUpperCase} //returns a String
"abcde" map {_.toInt} // returns an IndexedSeq[Int]
BitSet(1,2,3,4) map {2*} // returns a BitSet
BitSet(1,2,3,4) map {_.toString} // returns a Set[String]

Глядя в скаляр, все они используют map операция, унаследованная от TraversableLikeтак почему же он всегда может вернуть наиболее конкретную действительную коллекцию? Четное String, который обеспечивает map через неявное преобразование.

Answer 1

Коллекции Scala - это умные вещи...

Внутренняя часть коллекции библиотеки является одной из наиболее продвинутых тем в земле Скала. Он включает в себя более родственные типы, умозаключения, дисперсию, последствия и CanBuildFrom механизм - все, чтобы сделать его невероятно универсальным, простым в использовании и мощным с точки зрения пользователя. Понимание этого с точки зрения дизайнера API - не легкая задача для начинающего.

С другой стороны, невероятно редко когда-либо вам действительно нужно работать с коллекциями на такой глубине.

Итак, давайте начнем...

С выпуском Scala 2.8 библиотека коллекций была полностью переписана для устранения дублирования, огромное количество методов было перенесено в одно место, так что текущее обслуживание и добавление новых методов сбора было бы намного проще, но это также усложняет иерархию чтобы понять.

принимать List например, это наследуется от (в свою очередь)

• LinearSeqOptimised
• GenericTraversableTemplate
• LinearSeq
• Seq
• SeqLike
• Iterable
• IterableLike
• Traversable
• TraversableLike
• TraversableOnce

Это довольно горстка! Так почему эта глубокая иерархия? Игнорирование XxxLike Кратко говоря, каждый уровень в этой иерархии добавляет немного функциональности или предоставляет более оптимизированную версию унаследованной функциональности (например, выборка элемента по индексу в Traversable требует комбинации drop а также head операции, крайне неэффективные по индексируемой последовательности). Там, где это возможно, вся функциональность продвигается как можно дальше вверх по иерархии, максимизируя количество подклассов, которые могут ее использовать, и удаляя дублирование.

map это только один такой пример. Метод реализован в TraversableLike (Хотя XxxLike черты действительно существуют только для разработчиков библиотек, поэтому обычно считается, что метод Traversable для большинства намерений и целей - я скоро приду к этой части), и широко наследуется. Можно определить оптимизированную версию в некотором подклассе, но она все равно должна соответствовать той же сигнатуре. Рассмотрим следующие варианты использования map (как также упоминалось в вопросе):

"abcde" map {_.toUpperCase} //returns a String
"abcde" map {_.toInt} // returns an IndexedSeq[Int]
BitSet(1,2,3,4) map {2*} // returns a BitSet
BitSet(1,2,3,4) map {_.toString} // returns a Set[String]

В каждом случае выход имеет тот же тип, что и вход, где это возможно. Когда это невозможно, суперклассы типа ввода проверяются до тех пор, пока не будет найден один, который предлагает действительный тип возврата. Чтобы сделать это правильно, потребовалось много работы, особенно если учесть, что String это даже не коллекция, она просто неявно конвертируется в одну.

Так как это сделать?

Одна половина головоломки XxxLike черты (я сказал, что я доберусь до них...), чья основная функция состоит в том, чтобы взять Repr введите param (сокращение от "Представление"), чтобы они знали истинный подкласс, на котором фактически выполняется операция. Так, например, TraversableLike такой же как Traversable, но абстрактно Repr введите param. Этот параметр затем используется второй половиной головоломки; CanBuildFrom класс типа, который захватывает тип исходной коллекции, тип целевого элемента и тип целевой коллекции, которая будет использоваться операциями преобразования коллекции.

Это проще объяснить на примере!

BitSet определяет неявный экземпляр CanBuildFrom как это:

implicit def canBuildFrom: CanBuildFrom[BitSet, Int, BitSet] = bitsetCanBuildFrom

При компиляции BitSet(1,2,3,4) map {2*}компилятор попытается неявный поиск CanBuildFrom[BitSet, Int, T]

Это умная часть... Есть только один неявный в области видимости, который соответствует первым двум параметрам типа. Первый параметр Repr, как захвачено XxxLike trait, а второй тип элемента, как захвачено текущей особенностью коллекции (например, Traversable). map Затем операция также параметризируется с типом, этот тип T выводится на основе параметра третьего типа CanBuildFrom экземпляр, который был неявно расположен. BitSet в этом случае.

Итак, первые два типа параметров CanBuildFrom являются входами, которые будут использоваться для неявного поиска, а третий параметр является выходом, который будет использоваться для вывода.

CanBuildFrom в BitSet поэтому соответствует двум типам BitSet а также Int, так что поиск будет успешным, и предполагаемый тип возврата также будет BitSet,

При компиляции BitSet(1,2,3,4) map {_.toString}компилятор попытается неявный поиск CanBuildFrom[BitSet, String, T], Это не удастся для неявного в BitSet, поэтому компилятор в следующий раз попробует свой суперкласс - Set - Это содержит неявное:

implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, Set[A]] = setCanBuildFrom[A]

Что соответствует, потому что Coll является псевдонимом типа, который инициализируется как BitSet когда BitSet происходит от Set, A будет соответствовать чему угодно, как canBuildFrom параметризован с типом Aв данном случае предполагается, что String... Таким образом, получая тип возврата Set[String],

Таким образом, чтобы правильно реализовать тип коллекции, вам нужно не только предоставить правильный неявный тип CanBuildFrom, но вы также должны убедиться, что конкретный тип этой коллекции поставляется как Repr param для правильных родительских черт (например, это будет MapLike в случае подклассов Map).

String немного сложнее, поскольку это обеспечивает map неявным преобразованием. Неявное преобразование заключается в StringOpsкакие подклассы StringLike[String]что в конечном итоге выводит TraversableLike[Char,String] - String быть Repr введите param.

Там также есть CanBuildFrom[String,Char,String] в области видимости, так что компилятор знает, что при отображении элементов String в Chars, тогда тип возвращаемого значения также должен быть строкой. С этого момента и далее используется тот же механизм.

Answer 2

Онлайн-страницы " Архитектура коллекций Scala" содержат подробное объяснение практических аспектов создания новых коллекций на основе дизайна коллекции 2.8.

Цитата:

"Что нужно сделать, если вы хотите интегрировать новый класс коллекции, чтобы он мог получать прибыль от всех предопределенных операций для правильных типов? На следующих нескольких страницах вы пройдете через два примера, которые делают это".

В качестве примера он использует коллекцию для кодирования последовательностей РНК и одну для Patricia trie. Ищите раздел " Работа с картой и друзьями ", чтобы узнать, что нужно сделать, чтобы вернуть соответствующий тип коллекции.