Scala. Профессиональное программирование 2022. Одерски Мартин, Спун Лекс, Веннерс Билл, Соммерс ФрэнкО41 Scala. Профессиональное программирование. 5е изд спб. Питер, 2022. 608 с. ил. Серия Библиотека программиста
 Скачать 6.24 Mb.
|
|
302 Глава 14 • Работа со списками которая работает так: для сортировки непустого списка x :: xs сортируется остаток xs и первый элемент x вставляется в нужную позицию результата. Таблица 14.1. Основные операции над списками Что используется Что этот метод делает empty.isEmpty Возвращает true fruit.isEmpty Возвращает false fruit.head Возвращает "apples" fruit.tail.head Возвращает "oranges" diag3.head Возвращает List(1, 0, 0) Сортировка пустого списка выдает пустой список. Выраженный в виде кода Scala, алгоритм сортировки вставками выглядит так, как показано в листин ге 14.1. Листинг 14.1. Сортировка списка List[Int] с помощью алгоритма сортировки вставками def isort(xs: List[Int]): List[Int] = if xs.isEmpty then Nil else insert(xs.head, isort(xs.tail)) def insert(x: Int, xs: List[Int]): List[Int] = if xs.isEmpty || x <= xs.head then x :: xs else xs.head :: insert(x, xs.tail) 14 .5 . Паттерны-списки Разбирать списки можно и с помощью сопоставления с образцом. Паттерны списки по порядку следования соответствуют выражениям списков. Исполь зуя паттерн вида List(...) , можно либо сопоставить все элементы списка, либо разобрать список поэлементно, применив паттерны, составленные из оператора :: и константы Nil Пример использования первой разновидности паттерна выглядит следу ющим образом: scala> val List(a, b, c) = fruit val a: String = apples val b: String = oranges val c: String = pears 14 .5 . Паттерны-списки 303 Паттерн List(a, b, c) соответствует спискам длиной три элемента и привя зывает эти три элемента к паттернампеременным a , b и c . Если количество элементов заранее не известно, то лучше вместо этого сопоставлять с помо щью оператора :: . Например, паттерн a :: b :: rest соответствует спискам длиной два и более элемента: scala> val a :: b :: rest = fruit val a: String = apples val b: String = oranges val rest: List[String] = List(pears) О сопоставлении с образцом объектов класса List Если провести беглый обзор возможных форм паттернов, рас смотренных в главе 15, то выяснится, что ничего похожего ни на List(...) , ни на :: в определенных там разновидностях нет. Фак тически List(...) — экземпляр определенного в библиотеке пат тернаэкстрактора. Конспаттерн x :: xs — особый случай паттерна инфиксной операции. В качестве выражения инфиксная операция выступает эквивалентом вызова метода. Для паттернов действуют иные правила: в качестве паттерна такая инфиксная операция, как p op q , является эквивалентом op(p, q) . То есть инфиксный оператор op рассматривается в качестве паттернаконструктора. В частности, такой конспаттерн, как x :: xs , рассматривается как ::(x, xs) Это обстоятельство подсказывает, что должен быть класс по имени :: , соответствующий паттернуконструктору. Разумеется, это существу ющий одноименный класс, который создает непустые списки. Следо вательно, :: в Scala фигурирует дважды: как имя класса и как метод класса List . Результатом применения метода :: является создание экземпляра класса scala.:: Извлечение части списков с помощью паттернов — альтернатива использо ванию основных методов head , tail и isEmpty . Например, в коде ниже снова применена сортировка вставками, на этот раз записанная с сопоставлением с образцом: def isort(xs: List[Int]): List[Int] = xs match case List() => List() case x :: xs1 => insert(x, isort(xs1)) def insert(x: Int, xs: List[Int]): List[Int] = 304 Глава 14 • Работа со списками xs match case List() => List(x) case y :: ys => if x <= y then x :: xs else y :: insert(x, ys) Зачастую применение к спискам сопоставления с образцом оказывается более понятным, чем их декомпозиция с помощью методов, поэтому данное сопоставление должно стать частью вашего инструментария для обработки списков. Вот и все, что нужно знать о списках в Scala, чтобы их правильно применять. Но существует также множество методов, которые вбирают в себя наиболее распространенные схемы проведения операций со списками. Эти методы делают программы обработки списков более лаконичными и зачастую более понятными. В следующих двух разделах мы представим наиболее важные методы, определенные в классе List 14 .6 . Методы первого порядка класса List В этом разделе мы рассмотрим большинство определенных в классе List методов первого порядка. Метод первого порядка не получает в качестве аргументов никаких функций. Мы также представим несколько рекомен дованных приемов структурирования программ, работающих со списками, на двух примерах. Конкатенация двух списков Операцией, похожей на :: , является конкатенация списков, записываемая в виде ::: . В отличие от операции :: операция ::: получает в качестве операндов два списка. Результатом выполнения кода xs ::: ys выступает новый список, содержащий все элементы списка xs , за которыми следуют все элементы списка ys Рассмотрим несколько примеров: List(1, 2) ::: List(3, 4, 5) // List(1, 2, 3, 4, 5) List() ::: List(1, 2, 3) // List(1, 2, 3) List(1, 2, 3) ::: List(4) // List(1, 2, 3, 4) Как и консоператор, конкатенация списков правоассоциативна. Такое вы ражение, как xs ::: ys ::: zs 14 .6 . Методы первого порядка класса List 305 интерпретируется следующим образом: xs ::: (ys ::: zs) Принцип «разделяй и властвуй» Конкатенация ( ::: ) реализована в виде метода класса List . Можно было бы также реализовать конкатенацию «вручную», используя сопоставле ние с образцом для списков. Будет поучительно попробовать сделать это самостоятельно, поскольку таким образом можно проследить общий путь реализации алгоритмов с помощью списков. Сначала мы остановимся на сигнатуре метода конкатенации, который назовем append . Чтобы не созда вать большой путаницы, предположим, что append определен за пределами класса List , поэтому будет получать в качестве параметров два конкатени руемых списка. Оба они должны быть согласованы по типу их элементов, но сам тип может быть произвольным. Все это можно обеспечить, задав append параметр типа 1 , представляющего тип элементов двух исходных списков: def append[T](xs: List[T], ys: List[T]): List[T] Чтобы спроектировать реализацию append , имеет смысл вспомнить прин цип «разделяй и властвуй» для программ, работающих с рекурсивными структурами данных, такими как списки. Многие алгоритмы для работы со списками сначала разбивают исходный список на простые блоки, ис пользуя сопоставление с образцом. Это часть принципа, которая называ ется «разделяй». Затем конструируется результат для каждого варианта. Если результатом является непустой список, то некоторые из его частей можно сконструировать с помощью рекурсивных вызовов того же самого алгоритма. В этом будет заключаться часть принципа, называемая «вла- ствуй». Чтобы применить этот принцип к реализации метода append , сначала стоит ответить на вопрос: какой именно список нужно сопоставлять? При менительно к append данный вопрос не настолько прост, как для многих других методов, поскольку здесь имеются два варианта. Но следующая далее фаза «властвования» подсказывает: нужно сконструировать список, состоящий из всех элементов обоих исходных списков. Списки констру ируются из конца в начало, поэтому ys можно оставить нетронутым, а вот xs нужно разобрать и пристроить впереди ys . Таким образом, имеет смысл 1 Более подробно параметры типов будут рассмотрены в главе 18. 306 Глава 14 • Работа со списками сконцентрироваться на xs как на источнике сопоставления с образцом. Самое частое сопоставление в отношении списков просто отличает пустой список от непустого. Итак, для метода append вырисовывается следующая схема: def append[T](xs: List[T], ys: List[T]): List[T] = xs match case List() => ??? case x :: xs1 => ??? Остается лишь заполнить два места, обозначенных ??? 1 . Первое такое ме сто — альтернатива для случая, когда входной список xs пуст. В таком случае результатом конкатенации будет второй список: case List() => ys Второе место, оставленное незаполненным, — альтернатива для случая, когда входной список xs состоит из некоего head элемента x , за которым следует остальная часть xs1 . В таком случае результатом тоже будет непустой спи сок. Чтобы сконструировать непустой список, нужно знать, какой должна быть его «голова» (head), а каким — «хвост» (tail). Вам известно, что первый элемент получающегося в результате списка — x . Что касается остальных элементов, то их можно вычислить, добавив второй список, ys , к оставшейся части первого списка, xs1 Это завершает проектирование и дает: def append[T](xs: List[T], ys: List[T]): List[T] = xs match case List() => ys case x :: xs1 => x :: append(xs1, ys) Вычисление второй альтернативы — иллюстрация той части принципа, ко торая называется «властвуй»: сначала нужно продумать форму желаемого результата, затем вычислить отдельные части этой формы, используя, где возможно, рекурсивные вызовы алгоритма. И наконец, сконструировать из этих частей вывод. 1 ??? — это метод, который генерирует ошибку scala.NotImplementedError и имеет результирующий тип Nothing . Он может применяться в качестве временной реа лизации в процессе разработки приложения. 14 .6 . Методы первого порядка класса List 307 Получение длины списка: length Метод length вычисляет длину списка: List(1, 2, 3).length // 3 Определение длины списков, в отличие от массивов, — довольно затратная операция. Чтобы ее выполнить, нужно пройти по всему списку в поисках его конца, и на это затрачивается время, пропорциональное количеству элементов списка. Поэтому вряд ли имеет смысл заменять xs.isEmpty вы ражением xs.length == 0 . Результаты будут получены одинаковые, но второе выражение будет выполняться медленнее, в частности, если список xs имеет большую длину. Обращение к концу списка: init и last Вам уже известны основные операции head и tail , в результате выполне ния которых извлекаются соответственно первый элемент списка и весь остальной список, за исключением первого элемента. У каждой из них есть обратная по смыслу операция: last возвращает последний элемент непустого списка, а init — список, состоящий из всех элементов, за исключением по следнего: val abcde = List('a', 'b', 'c', 'd', 'e') abcde.last // e abcde.init // List(a, b, c, d) Подобно методам head и tail , эти методы, примененные к пустому списку, генерируют исключение: scala> List().init java.lang.UnsupportedOperationException: init of empty list at ... scala> List().last java.util.NoSuchElementException: last of empty list at ... В отличие от head и tail , на выполнение которых неизменно затрачивается одно и то же время, для вычисления результата методы init и last должны обойти весь список. То есть их выполнение требует времени, пропорцио нального длине списка. 308 Глава 14 • Работа со списками Неплохо было бы организовать ваши данные таким образом, чтобы основная часть обращений приходилось на головной, а не на послед ний элемент списка. Реверсирование списков: reverse Если в какойто момент вычисления алгоритма требуется часто обращаться к концу списка, то порой более разумным будет сначала перестроить список в обратном порядке и работать уже с результатом. Получить такой список можно следующим образом: abcde.reverse // List(e, d, c, b, a) Как и все остальные операции со списками, reverse создает новый список, а не изменяет тот, с которым работает. Поскольку списки неизменяемы, сде лать это все равно бы было невозможно. Чтобы убедиться в этом, убедитесь, что исходный список abcde после операции reverse не изменился: abcde // List(a, b, c, d, e) Операции reverse , init и last подчиняются ряду законов, с помощью кото рых можно анализировать вычисления и упрощать программы. 1. Операция reverse является собственной инверсией: xs.reverse.reverse равно xs 2. Операция reverse превращает init в tail , а last в head , за исключением того, что все элементы стоят в обратном порядке: xs.reverse.init равно xs.tail.reverse xs.reverse.tail равно xs.init.reverse xs.reverse.head равно xs.last xs.reverse.last равно xs.head Реверсирование можно реализовать, воспользовавшись конкатенацией ( ::: ), как в следующем методе по имени rev : def rev[T](xs: List[T]): List[T] = xs match case List() => xs case x :: xs1 => rev(xs1) ::: List(x) 14 .6 . Методы первого порядка класса List 309 Но этот метод, вопреки предположениям, менее эффективен. Чтобы убе диться в высокой вычислительной сложности rev , представьте, будто спи сок xs имеет длину n. Обратите внимание: придется делать n рекурсивных вызовов rev . Каждый вызов, за исключением последнего, влечет за собой конкатенацию списков. На конкатенацию xs ::: ys затрачивается время, пропорциональное длине ее первого аргумента xs . Следовательно, общая вычислительная сложность rev выражается так: n + (n – 1) + ... + 1 = (1 + n) × n / 2. Иными словами, rev имеет квадратичную вычислительную сложность по длине его входного аргумента. Если сравнить это обстоятельство со стандарт ным реверсированием изменяемого связного списка, имеющего линейную вычислительную сложность, то оно вызывает разочарование. Но данная реа лизация rev — не самая лучшая из возможных. Пример, который начинается на с. 321, позволит вам увидеть, как можно ускорить все это. Префиксы и суффиксы: drop, take и splitAt Операции drop и take обобщают tail и init в том смысле, что возвращают произвольные префиксы или суффиксы списка. Выражение xs.take(n) возвращает первые n элементов списка xs . Если n больше xs.length , то воз вращается весь список xs . Операция xs.drop(n) возвращает все элементы списка xs , за исключением первых n элементов. Если n больше xs.length , то возвращается пустой список. Операция splitAt разбивает список по заданному индексу, возвращая пару из двух списков 1 . Она определяется следующим равенством: xs.splitAt( n ) равно (xs.take( n ), xs.drop( n )) Но операция splitAt избегает двойного прохода по элементам списка. При меры применения этих трех методов выглядят следующим образом: abcde.take(2) // List(a, b) abcde.drop(2) // List(c, d, e) abcde.splitAt(2) // (List(a, b),List(c, d, e)) 1 Как уже упоминалось в разделе 10.12, понятие пары — неформальное название для Tuple2. 310 Глава 14 • Работа со списками Выбор элемента: apply и indices Произвольный выбор элемента поддерживается методом apply , но эта опе рация менее востребована, чем аналогичная операция для массивов: abcde.apply(2) // в Scala используется довольно редко Что же касается всех остальных типов, то подразумевается, что apply встав ляется в вызове метода, когда объект появляется в позиции функции. По этому показанную ранее строку кода можно сократить до следующей: abcde(2) // в Scala используется довольно редко Одной из причин того, что выбор произвольного элемента менее популярен для списков, чем для массивов, является то, что на выполнение кода xs(n) затрачивается время, пропорциональное величине значения индекса n . Фак тически метод apply определен сочетанием методов drop и head : xs.apply( n ) равно (xs.drop( n )).head Из этого определения также становится понятно, что индексы списков, как и индексы массивов, задаются в диапазоне от 0 до длины списка минус один. Метод indices возвращает список, состоящий из всех допустимых индексов заданного списка: abcde.indices // Диапазон от 0 до 5 Линеаризация списка списков: flatten Метод flatten принимает список списков и линеаризует его в единый спи сок: List(List(1, 2), List(3), List(), List(4, 5)).flatten // List(1, 2, 3, 4, 5) fruit.map(_.toList).flatten // List(a, p, p, l, e, s, o, r, a, n, g, e, // s, p, e, a, r, s) Он применим только к тем спискам, все элементы которых являются спи сками. Попытка линеаризации других списков выдаст ошибку компиляции: scala> List(1, 2, 3).flatten 1 |List(1, 2, 3).flatten | ˆ 14 .6 . Методы первого порядка класса List 311 | No implicit view available from | Int => IterableOnce[B] | where, B is a type variable. Объединение списков: zip и unzip Операция zip получает два списка и формирует список из пар их значений: abcde.indices.zip(abcde) // Vector((0,a), (1,b), (2,c), (3,d), (4,e)) Если списки разной длины, то все элементы без пары отбрасываются: val zipped = abcde.zip(List(1, 2, 3)) // List((a,1), (b,2), (c,3)) Особо полезен вариант объединения в пары списка с его индексами. Наи более эффективно оно выполняется с помощью метода zipWithIndex , со ставляющего пары из каждого элемента списка и той позиции, в которой он появляется в этом списке. abcde.zipWithIndex // List((a,0), (b,1), (c,2), (d,3), (e,4)) Любой список кортежей можно превратить обратно в кортеж списков с по мощью метода unzip : zipped.unzip // (List(a, b, c),List(1, 2, 3)) Методы zip и unzip реализуют один из способов одновременной работы с несколькими списками. Более эффективный способ сделать то же самое показан в разделе 14.9. Отображение списков: toString и mkString Операция toString возвращает каноническое строковое представление списка: abcde.toString // List(a, b, c, d, e) Если требуется иное представление, то можно воспользоваться методом mkString . Операция xs mkString (pre, sep, post) задействует четыре опе ранда: отображаемый список xs , префиксную строку pre , отображаемую перед всеми элементами, строковый разделитель sep , отображаемый между |