Scala. Профессиональное программирование 2022. Одерски Мартин, Спун Лекс, Веннерс Билл, Соммерс ФрэнкО41 Scala. Профессиональное программирование. 5е изд спб. Питер, 2022. 608 с. ил. Серия Библиотека программиста
 Скачать 6.24 Mb.
|
|
322 Глава 14 • Работа со списками Следовательно, стартовое_значение должно быть List() . Чтобы вывести второй операнд, в качестве примера можно взять следующий наименьший список. Поскольку уже известно, что стартовое_значение — это List() , мож но рассуждать так: List(x) равен (в понятиях свойств reverseLeft) reverseLeft(List(x)) равен (по схеме для reverseLeft со стартовым_значением = List()) List(x).foldLeft(List())(операция) равен (по определению foldLeft) операция (List(), x) Следовательно, операция(List(), x) — эквивалент List(x) , что можно за писать также в виде x :: List() . Это наводит на такую мысль: нужно взять в качестве операции оператор :: с его операндами, которые поменяли ме стами. (Иногда такую операцию называют «снок», ссылаясь на операцию :: , которую называют «конс».) И тогда мы приходим к следующей реализации метода reverseLeft : def reverseLeft[T](xs: List[T]) = xs.foldLeft(List[T]()) { (ys, y) => y :: ys } Чтобы заставить работать механизм вывода типов, здесь также в качестве аннотации типа требуется использовать код List[T]() . Если проанализиро вать вычислительную сложность reverseLeft , то можно прийти к выводу, что в нем n раз применяется постоянная по времени выполнения операция («снок»), где n — длина спискааргумента. Таким образом, вычислительная сложность reverseLeft линейна. Сортировка списков: sortWith Операция xs sortWith before , где xs — это список, а before — функция, которая может использоваться для сравнения двух элементов, выполняет сортировку элементов списка xs . Выражение x before y должно возвра щать true , если в желаемом порядке следования x должен стоять перед y , например: 14 .8 . Методы объекта List 323 List(1, -3, 4, 2, 6).sortWith(_ < _) // List(-3, 1, 2, 4, 6) words.sortWith(_.length > _.length) // List(quick, brown, the, fox) Обратите внимание: sortWith выполняет сортировку слиянием подобно тому, как это делает алгоритм msort , показанный в последнем разделе. Но sortWith является методом класса List , а msort определен вне списков. 14 .8 . Методы объекта List До сих пор все показанные в этой главе операции реализовывались в каче стве методов класса List , поэтому вызывались в отношении отдельно взятых списочных объектов. Существует также ряд методов в глобально доступном объекте scala.List , который является объектомкомпаньоном класса List Одни такие операции — это фабричные методы, создающие списки. Другие же — это операции, работающие со списками некоторых конкретных видов. В этом разделе будут представлены обе разновидности методов. Создание списков из их элементов: List .apply В книге уже несколько раз попадались литералы списков вида List(1, 2, 3) В их синтаксисе нет ничего особенного. Литерал вида List(1, 2, 3) — про стое применение объекта List к элементам 1 , 2 , 3 . То есть это эквивалент кода List.apply(1, 2, 3) : List.apply(1, 2, 3) // List(1, 2, 3) Создание диапазона чисел: List .range Метод range , который ранее подробно рассматривался при изучении методов map и flatmap , создает список, состоящий из диапазона чисел. Его самая про стая форма, при которой создаются все числа, начиная с from и заканчивая until минус один, — List.range(from, until) . Следовательно, последнее значение, until , в диапазон не входит. Существует также версия range , получающая в качестве третьего параметра значение step . В результате выполнения этой операции получится список элементов, которые следуют друг за другом с указанным шагом, начиная 324 Глава 14 • Работа со списками с from . Указываемый шаг step может иметь положительное или отрицатель ное значение: List.range(1, 5) // List(1, 2, 3, 4) List.range(1, 9, 2) // List(1, 3, 5, 7) List.range(9, 1, -3) // List(9, 6, 3) Создание единообразных списков: List .fill Метод fill создает список, состоящий из нуля или более копий одного и того же элемента. Он получает два параметра: длину создаваемого списка и по вторяемый элемент. Каждый параметр задается в отдельном списке: List.fill(5)('a') // List(a, a, a, a, a) List.fill(3)("hello") // List(hello, hello, hello) Если методу fill дать более двух аргументов, то он будет создавать много мерные списки, то есть списки списков, списки списков из списков и т. д. Дополнительный аргумент помещается в первый список аргументов. List.fill(2, 3)('b') // List(List(b, b, b), List(b, b, b)) Табулирование функции: List .tabulate Метод tabulate создает список, элементы которого вычисляются соглас но предоставляемой функции. Аргументы у него такие же, как и у метода List.fill : в первом списке аргументов задается размерность создаваемого списка, а во втором дается описание элементов списка. Единственное отли чие — элементы не фиксируются, а вычисляются из функции: val squares = List.tabulate(5)(n => n * n) // List(0, 1, 4, 9, 16) val multiplication = List.tabulate(5,5)(_ * _) // List(List(0, 0, 0, 0, 0), // List(0, 1, 2, 3, 4), List(0, 2, 4, 6, 8), // List(0, 3, 6, 9, 12), List(0, 4, 8, 12, 16)) Конкатенация нескольких списков: List .concat Метод concat объединяет несколько списков элементов. Конкатенируемые списки предоставляются concat в виде непосредственных аргументов: List.concat(List('a', 'b'), List('c')) // List(a, b, c) List.concat(List(), List('b'), List('c')) // List(b, c) List.concat() // List() 14 .9 . Совместная обработка нескольких списков 325 14 .9 . Совместная обработка нескольких списков Вы уже знакомы с методом zip , который создает список пар из двух списков, позволяя работать с ними одновременно: List(10, 20).zip(List(3, 4, 5))).map { (x, y) => x * y } // List(30, 80) ПРИМЕЧАНИЕ Последний map использует преимущества такой особенности Scala 3, как разгруппировка параметров, в которой литерал функции с двумя или более параметрами будет автоматически разгруппирован, если ожидаемый тип является функцией, которая принимает один параметр типа кортеж . На- пример, вызов map в предыдущем выражении означает то же самое, что и map { case (x, y) => x * y } Метод map , примененный к спискам, прошедшим через zip , перебирает не отдельные элементы, а их пары. Первая пара содержит элементы, идущие первыми в каждом списке, вторая — элементы, идущие вторыми, и т. д. Количество пар определяется длиной списков. Обратите внимание: третий элемент второго списка отбрасывается. Метод zip объединяет только то ко личество элементов, которое совместно появляется во всех списках. Любые лишние элементы в конце отбрасываются. Один из недостатков работы с несколькими списками с помощью метода zip состоит в том, что мы получаем промежуточный список (после вызова zip ), который в конечном счете отбрасывается (при вызове метода map ). Создание этого промежуточного списка может потребовать существенных расходов, если у него много элементов. Эти две проблемы решает метод lazyZip По своему синтаксису он похож на метод zip : (List(10, 20).lazyZip(List(3, 4, 5))).map(_ * _) // List(30, 80) Разница между lazyZip и zip в том, что первый не возвращает коллекцию сразу (отсюда и префикс lazy — «ленивый»). Вместо этого вы получаете значение, предоставляющее методы (включая map ) для работы с двумя спи сками, для которых метод zip выполнен отложенно. В приведенном выше примере вы можете видеть, как метод map принимает функцию с двумя параметрами (вместо одной пары), позволяя нам использовать синтаксис заместителей. 326 Глава 14 • Работа со списками Существуют также обобщающие аналоги для методов exists и forall . Они похожи на версии этих методов, предназначенные для работы с одним спи ском, но оперируют элементами не одного, а нескольких списков: (List("abc", "de").lazyZip(List(3, 2))).forall(_.length == _) // true (List("abc", "de").lazyZip(List(3, 2))).exists(_.length != _) // false УСКОРЕННЫЙ РЕЖИМ ЧТЕНИЯ В последнем разделе этой главы дается информация об имеющемся в Scala алгоритме вывода типов . Если такие подробности сейчас вас не интересу- ют, то можете пропустить весь раздел и сразу перейти к резюме на с . 330 . 14 .10 . Понимание имеющегося в Scala алгоритма вывода типов Одно из отличий предыдущего использования sortWith и msort касается допустимых синтаксических форм функции сравнения. Сравните этот диалог с интерпретатором: msort((x: Char, y: Char) => x > y)(abcde) // List(e, d, c, b, a) со следующим: abcde.sortWith(_ > _) // List(e, d, c, b, a) Эти два выражения эквивалентны, но в первом используется более длинная форма функции сравнения с именованными параметрами и явно заданными типами. Во втором задействована более краткая форма, (_ > _) , в которой вместо именованных параметров стоят знаки подчеркивания. Разумеется, с методом sortWith вы можете применить также первую, более длинную форму сравнения. А вот с msort более краткая форма использоваться не может: scala> msort(_ > _)(abcde) 1 |msort(_ > _)(abcde) | ˆˆˆ |value > is not a member of Any, but could be made | available as an extension method. 14 .10 . Понимание имеющегося в Scala алгоритма вывода типов 327 Чтобы понять, почему именно так происходит, следует знать некоторые подробности имеющегося в Scala алгоритма вывода типов. Это поточный ме ханизм. При использовании метода m(args) механизм вывода типов сначала проверяет, имеется ли известный тип у метода m . Если да, то именно он и при меняется для вывода ожидаемого типа аргументов. Например, в выражении abcde.sortWith(_ > _) типом abcde является List[Char] . Таким образом, sortWith известен как метод, получающий аргумент типа (Char, Char) => Boolean и выдающий результат типа List[Char] . Поскольку типы параметров аргументов функции известны, то их не нужно записывать явным образом. По совокупности всего известного о методе sortWith механизм вывода типов может установить, что код (_ > _) нужно раскрыть в ((x: Char, y: Char) => x > y) , где x и y — некие произвольные только что полученные имена. Теперь рассмотрим второй вариант, msort(_ > _)(abcde) . Типом msort являет ся каррированный полиморфный тип метода, который принимает аргумент типа (T, T) => Boolean в функцию из List[T] в List[T] , где T — некий пока еще неизвестный тип. Прежде чем он будет применен к своим аргументам, у метода msort должен быть создан экземпляр с параметром типа. Точный тип экземпляра msort в приложении еще неизвестен, поэтому он не может быть использован для вывода типа своего первого аргумента. В этом случае механизм вывода типов меняет свою стратегию: сначала он проверяет тип аргументов метода для определения экземпляра метода с подходящим типом. Но когда перед ним стоит задача проверки типа функционального литерала в краткой форме записи, (_ > _) , он дает сбой изза отсутствия информации о неявных типах заданных параметров функции, показанных знаками подчеркивания. Один из способов решить проблему — передать msort явно заданный тип параметра: msort[Char](_ > _)(abcde) // List(e, d, c, b, a) Экземпляр msort подходящего типа теперь известен, поэтому его можно использовать для вывода типов аргументов. Еще одним потенциальным решением может стать перезапись метода msort таким образом, чтобы его параметры поменялись местами: def msortSwapped[T](xs: List[T])(less: (T, T) => Boolean): List[T] = ... // та же реализация, что и у msort, // но с аргументами, которые поменялись местами 328 Глава 14 • Работа со списками Теперь вывод типов будет выполнен успешно: msortSwapped(abcde)(_ > _) // List(e, d, c, b, a) Получилось так, что механизм вывода типов воспользовался известным типом первого параметра abcde , чтобы определить параметр типа метода msortSwapped . Точный тип msortSwapped был известен, поэтому с его помо щью может быть выведен тип второго параметра, (_ > _) В общем, когда ставится задача вывести параметры типа полиморфного ме тода, механизм вывода типов принимает во внимание типы всех значений аргументов в первом списке параметров, игнорируя все аргументы, кроме этих. Поскольку msortSwapped — каррированный метод с двумя списками параметров, то не нужно обращать внимание на второй аргумент (то есть на функциональное значение), чтобы определить параметр типа метода. Эта схема вывода типов предлагает следующий принцип разработки библио тек: при разработке полиморфного метода, который получает некие нефунк циональные аргументы и функциональный аргумент, этот функциональный аргумент в самом каррированном списке параметров нужно поставить на последнее место. Тогда экземпляр метода подходящего типа можно выве сти из нефункциональных аргументов, и этот тип, в свою очередь, можно использовать для проверки типа функционального аргумента. Совокупный эффект будет состоять в том, что пользователи метода получат возможность предоставить меньший объем информации и написания функциональных литералов более компактными способами. Теперь рассмотрим более сложный случай, касающийся операции свертки. Почему необходимо явно указывать параметр типа в выражении, подобном телу метода flattenRight , показанного на с. 320–321? xss.foldRight(List[T]())(_ ::: _) Тип метода flattenRight полиморфен в двух переменных типа. Если взять выражение xs.foldRight(z)(op) то типом xs должен быть список какогото произвольного типа A , скажем xs: List[A] . Начальное значение z может быть какогонибудь другого типа B Тогда операция op должна получать два аргумента типа, A и B , и возвращать результат типа B , то есть op: (A, B) => B . Тип значения z не связан с типом списка xs , поэтому у механизма вывода типов нет контекстной информации для z 14 .10 . Понимание имеющегося в Scala алгоритма вывода типов 329 Теперь рассмотрим выражение в ошибочной версии метода flattenRight : xss.foldRight(List())(_ ::: _) // этот код не пройдет компиляцию Начальное значение z в данной свертке — пустой список, List() , следова тельно, при отсутствии дополнительной информации о типе его тип будет выведен как List[Nothing] . Исходя из этого, механизм вывода типов уста новит, что типом B в свертке будет являться List[Nothing] . Таким образом, для операции (_ ::: _) в свертке будет ожидаться следующий тип: (List[T], List[Nothing]) => List[Nothing] Конечно же, такой тип возможен для операции в данной свертке, но пользы от него никакой! Он сообщает, что операция всегда получает в качестве вто рого аргумента пустой список и всегда в качестве результата выдает также пустой список. Иными словами, вопрос вывода типов на основе List() был решен слиш ком рано — он должен был выждать, пока не станет виден тип операции op Следовательно, весьма полезное в иных случаях правило о том, что для определения типа метода нужно принимать во внимание только первый список аргументов, будучи применен к каррированному методу, становится камнем преткновения. В то же время, даже если бы это правило было смяг чено, механизм вывода типов все равно не смог бы определиться с типом для операции op , поскольку ее типы параметров не приведены. Таким образом, создается ситуация, как в уловке22 1 , которую можно разрешить с помощью явной аннотации типа, получаемой от программиста. Данный пример выявляет ряд ограничений локальной, поточной схемы вывода типов, имеющейся в Scala. В более глобальном механизме вывода типов в стиле Хиндли — Милнера (Hindley — Milner), используемом в та ких функциональных языках, как ML или Haskell, подобных ограничений нет. Но по сравнению со стилем Хиндли — Милнера имеющийся в Scala механизм вывода типов обходится с объектноориентированной системой подтипов намного изящнее. К счастью, ограничения проявляются только в некоторых крайних случаях, и обычно их без особого труда можно обойти, добавив явную аннотацию типа. 1 Уловка22 (Catch22) — ситуация, возникающая в результате логического пара докса между взаимоисключающими правилами и процедурами. В этой ситуации индивид, подпадающий под действие таких норм, не может их никак контролиро вать, так как попытка нарушить эти установки автоматически подразумевает их соблюдение. 330 Глава 14 • Работа со списками Добавление аннотаций типа пригодится также при отладке, когда вас по ставят в тупик сообщения об ошибках типа, связанных с полиморфными методами. Если вы не уверены в причине возникновения конкретной ошиб ки типа, то нужно просто добавить некоторые аргументы типа или другие аннотации типа, в правильности которых вы не сомневаетесь. Тогда можно будет быстро понять, где реальный источник проблемы. Резюме В этой главе мы показали множество способов работы со списками. Рассмо трели основные операции, такие как head и tail ; операции первого порядка, такие как reverse ; операции высшего порядка, такие как map ; и вдобавок полезные методы, определенные в объекте List . Попутно мы изучили прин ципы работы имеющегося в Scala механизма вывода типов. Списки в Scala — настоящая рабочая лошадка, поэтому, узнав, как с ними ра ботать, вы сможете извлечь для себя немалую выгоду. Именно с этой целью мы в данной главе погрузились в способы применения списков. Но списки — всего лишь одна из разновидностей коллекций, поддерживаемых в Scala. Тематика следующей главы будет скорее охватывающей, чем углубленной. В ней мы покажем вам порядок использования различных типов коллекций Scala. 15 Работа с другими коллекциями В Scala содержится весьма богатая библиотека коллекций. В этой главе мы расскажем о наиболее часто используемых типах коллекций и операциях над ними. 15 .1 . Последовательности Типы последовательностей позволяют работать с группами данных, выстро енных по порядку. Поскольку элементы упорядочены, то можно запрашивать первый элемент, второй, 103й и т. д. В этом разделе мы бегло пройдемся по наиболее важным последовательностям. Списки Возможно, самым важным типом последовательности, о котором следует знать, является класс List — неизменяемый связный список, подробно рас смотренный в предыдущей главе. Списки поддерживают быстрое добавление и удаление элементов в начало списка, но не позволяют получить быстрый доступ к произвольным индексам, поскольку, чтобы это реализовать, требу ется выполнить последовательный обход всех элементов списка. Такое сочетание свойств может показаться странным, но оно попало в золо тую середину и неплохо функционирует во многих алгоритмах. Как следует из описаний, представленных в данной главе, быстрое добавление и удаление начальных элементов означает хорошую работу сопоставления с образцом. Неизменяемость списков помогает разрабатывать корректные эффективные алгоритмы, поскольку избавляет от необходимости создавать копии списков. |