Ваш вопрос на самом деле выглядит как два разных вопроса:
Как сконструированы стандартные библиотеки Scala и, в частности, как zipWithIndex работает?
Как реализовать мой пользовательский minWithIndex?
К сожалению, первый вопрос, вероятно, сложнее, чем второй.
Дизайн коллекций Scala
Начиная с версии 2.12, текущая scala.collection разработана, чтобы быть очень гибкой, но она требует затрат на использование многих расширенных функций и / или шаблонов проектирования.Также можно утверждать, что она чрезмерно спроектирована для использования в реальных условиях, и поэтому ее трудно понять новичку в Scala.
Проектирование библиотеки коллекций - известная трудная проблема, поскольку в идеале вы хотите захватить много разныхаспекты.Главное, что вы, вероятно, хотите охватить как можно больше аспектов, но в то же время иметь как можно меньше дублирования кода.(Например, рассмотрите связанный список против списка на основе массива. Оба, вероятно, должны иметь метод, подобный indexOf, который может быть реализован в терминах size и getByIndex, поэтому в идеале вы хотели бы иметь только одну реализацию здесь.)Это реальная проблема дизайна.
Вот неисчерпывающий список аспектов, которые повлияли на дизайн коллекций Scala (вы также можете найти некоторые заметки по дизайну в более ранней (2.8) версии здесь ):
Унифицированные интерфейсы для различных структур данных, реализующих сходные вещи (например, связанный список или список на основе массива очень похожи, в то время как связанный список и набор на основе дерева гораздо менее похожино все же есть что-то общее).Это является причиной различных признаков, таких как Seq или GenTraversableLike и иерархии глубокого наследования.
Тип-безопасность.Мы хотим, чтобы список целых чисел отличался от списка строк.И мы хотели бы знать тип хранимых элементов.Вот почему все коллекции являются общими.
Производительность.В каждом языке стандартные коллекции являются одним из наиболее часто используемых фрагментов кода, поэтому хорошая производительность очень важна.По этой причине в некоторых местах существует «нечистая» изменчивая реализация для чисто неизменяемых интерфейсов FP.
Отдельные коллекции только для чтения и изменяемые коллекции (особенно важно в языках FP)но и в других тоже).Вот почему существуют пакеты scala.collection, scala.collection.mutable и scala.collection.immutable.
Поддержка потенциально неограниченных последовательностей, таких как сгенерированные (числа Фибоначчи) или поступающие из внешнего источника (такого каккак последовательность байтов, прочитанных с консоли ввода).Это причина для таких вещей, как TraversableOnce или Iterable.
Поддержка последовательностей, которые нельзя (легко) обработать дважды.Например, поток всех сделок на какой-либо крупной фондовой бирже настолько велик, что его невозможно сохранить и повторно обработать.Это причина для TraversableOnce против Traversable
Внутренняя и внешняя итерация (это причина разделения между Iterable против Traversable)
Жадные и ленивые вычисления (это причина для типов с суффиксом «Просмотр»)
Поддержка объектов, подобных коллекциям, которые не являются коллекциями.Например, вы реализуете HTML-парсер или даже браузер.Многие HTML-элементы могут иметь детей, но не является основной обязанностью.Это является причиной различных черт с префиксом 'Gen`.
Теперь вернемся к zipWithIndex.Это один из многих методов (другие подобные map, fitler и многие другие), которые создают дополнительные проблемы для дизайнеров: эти методы создают новую коллекцию из текущей.С одной стороны, такие методы могут быть реализованы в общем случае один раз для всех коллекций, с другой стороны, при наивной реализации мы потеряем конкретные типы и, что еще хуже, нас могут заставить изменить реализацию и, следовательно, семантику.Рассмотрим наивную реализацию метода filter:
trait Iterable[A] {
def filter(p: A => Boolean): ? = {
var res: List[A] = Nil
for (x <- this)
if (p(x)) res = x :: res
res
}
}
Какой тип возврата поставить вместо ??Если мы просто введем Iterable[A], это означает, что мы сразу утратили возможность использовать все методы List, которые недоступны в Iterable (например, доступ по индексу).Но другое дело, что если бы наш Iterable на самом деле был Set.Мы, вероятно, хотим, чтобы результат filter снова был Set вместо List.Это то, что в приведенной выше статье называется " принцип одного и того же результата ".Scala - один из немногих языков, который позволяет вам разработать элегантное решение этой проблемы с минимальным дублированием кода.Основная идея заключается в том, чтобы иметь объект-компаньон для каждой реализации (например, Iterable и immutable.List ), а также признак-компаньон для каждой промежуточной характеристики (например, SeqFactory *).1105 *. Одной из важнейших возможностей, предоставляемых этими компаньонами, является возможность создания нового экземпляра "той же" коллекции (возможно, с другим универсальным типом).
И последнеев упомянутой статье не указан неявный параметр CanBuildFrom. Логика заключается в следующем: предположим, что у вас есть связанный список (List) и вы хотите, чтобы список на основе массива (Vector) был заархивирован.с индексом. Вам нужно создать промежуточный связанный список, упакованный с индексом в процессе? CanBuildFrom - это хитрость, которая позволяет ответить так: нет, вам не нужно. Неявные параметры - довольно продвинутая функцияScala, и вы, вероятно, должны прочитать больше об этом, если вы еще не знакомы. Идея состоит в том, что компилятор может автоматически искать параметрсоответствующего типа.Поэтому, если есть какое-либо значение, соответствующее типу, это область действия, код скомпилируется.Это означает, что наличие CanBuildFrom может использоваться как свидетельство , что вы можете изменить базовую структуру данных коллекции одновременно с некоторыми манипуляциями с данными (zipWithIndex, map, filter и т. Д.).Каждый сопутствующий объект предоставляет значение CanBuildFrom по умолчанию с одинаковой целевой структурой данных (например, см. immutable.List.canBuildFrom ).
Итак, теперь мы можем видеть, как IterableLike.zipWithIndex, чтореализована реализация по умолчанию для всех подтипов,
def zipWithIndex[A1 >: A, That](implicit bf: CanBuildFrom[Repr, (A1, Int), That]): That = {
val b = bf(repr)
var i = 0
for (x <- this) {
b += ((x, i))
i += 1
}
b.result()
}
Подпись гласит, что с помощью zipWithIndex вы можете преобразовать свою коллекцию Repr из A в That - коллекцию кортежей (A1, Int)до тех пор, пока
A1 является супертипом A (что является безопасным повышением) - У вас есть доказательства того, что вы можете построить
That из Repr(объект bf)
И что метод делает, он запрашивает bf свидетельство для создания b - нового Builder[(A1, Int), That], затем заполняет конструктор кортежами и, наконец,вернуть коллекцию That от застройщика (b.result()).И Builder, и for с var i используются для повышения производительности.
Как реализовать свой собственный minWithIndex
Ответ зависит от того, насколько универсальным вы хотите быть и насколько высока производительность.важно для тебя.Вот несколько вариантов:
implicit class MinWithIndexOps[A, Repr <: IterableLike[A, Repr]](it: IterableLike[A, Repr]) {
def minWithIndexWithZip[B >: A](implicit cmp: Ordering[B], bf: CanBuildFrom[Repr, (A, Int), Iterable[(A, Int)]]): (A, Int) = it.zipWithIndex(bf).min(Ordering.by[(A, Int), B]((kv: (A, Int)) => kv._1))
def minWithIndexWithFold[B >: A](implicit cmp: Ordering[B]): (A, Int) = {
if (it.isEmpty)
throw new UnsupportedOperationException("empty.min")
val h = it.head
val res = it.foldLeft((h, 0, 0))((acc, cur) => acc match {
case (minVal, minIndex, curIndex) => if (cmp.lteq(minVal, cur)) (minVal, minIndex, curIndex + 1) else (cur, curIndex, curIndex + 1)
})
(res._1, res._2)
}
def minWithIndexWithVars[B >: A](implicit cmp: Ordering[B]): (A, Int) = {
if (it.isEmpty)
throw new UnsupportedOperationException("empty.min")
var minVal = it.head
var minIndex = 0
var i = 0
for (cur <- it) {
if (cmp.gt(minVal, cur)) {
minVal = cur
minIndex = i
}
i += 1
}
(minVal, minIndex)
}
}
def test(): Unit = {
val data = "qwerty" :: "asdfg" :: "zxcvb" :: Nil
println(data.minWithIndexWithZip)
println(data.minWithIndexWithFold)
println(data.minWithIndexWithVars)
}
Обратите внимание, что здесь ключевое слово implicit используется в другом значении для создания implicit class, который эффективно расширяет каждый экземпляр IterableLike новыми методами.
Первая реализация minWithIndexWithZip очень проста, но, вероятно, очень неэффективна: сначала вы буквально делаете zipWithIndex, а затем вызываете min (обратите внимание также, что стандарт min использует необычное для Scala соглашение о создании исключения вместо возврата Option[A] и я использовал ту же семантику в других реализациях).Этот метод неэффективен, потому что вам нужно создать целую новую коллекцию, чтобы ее можно было утилизировать практически сразу.
minWithIndexWithFold - это другая реализация, которая не полагается на zipWithIndex и использует вместо нее foldLeft.fold является одновременно очень простой и очень общей операцией.Одним из преимуществ этого кода является то, что он также неизменен.Но из-за этого его производительность также не очень хорошая: множество промежуточных объектов-аккумуляторов будут созданы и уничтожены практически сразу.
Последняя minWithIndexWithVars, вероятно, наименее «чистая», но наиболее производительная версия, в которой используется простой императивный код.