Scala. Профессиональное программирование 2022. Одерски Мартин, Спун Лекс, Веннерс Билл, Соммерс ФрэнкО41 Scala. Профессиональное программирование. 5е изд спб. Питер, 2022. 608 с. ил. Серия Библиотека программиста
 Скачать 6.24 Mb.
|
|
312 Глава 14 • Работа со списками последовательно выводимыми элементами, и постфиксную строку, отобра жаемую в конце. Результатом операции будет следующая строка: pre + xs(0) + sep + . . . + sep + xs(xs.length - 1) + post У метода mkString имеется два перегруженных варианта, которые позволяют отбрасывать некоторые или все его аргументы. Первый вариант получает только строковый разделитель: xs.mkString(sep) равно xs.mkString("", sep, "") Второй вариант позволяет опустить все аргументы: xs.mkString равно xs.mkString("") Рассмотрим несколько примеров: abcde.mkString("[", ",", "]") // [a,b,c,d,e] abcde.mkString("") // abcde abcde.mkString // abcde abcde.mkString("List(", ", ", ")") // List(a, b, c, d, e) Есть также вариант mkString , называющийся addString ; он не возвра щает созданную строку в качестве результата, а добавляет ее к объекту StringBuilder 1 : val buf = new StringBuilder abcde.addString(buf, "(", ";", ")") // (a;b;c;d;e) Методы mkString и addString наследуются из супертрейта Iterable класса List , поэтому их можно применять ко всем другим коллекциям. Преобразование списков: iterator, toArray, copyToArray Чтобы выполнить преобразование данных между линейным миром массивов и рекурсивным миром списков, можно воспользоваться методом toArray в классе List и методом toList в классе Array : val arr = abcde.toArray // Array(a, b, c, d, e) arr.toList // List(a, b, c, d, e) 1 Имеется в виду класс scala.StringBuilder , а не java.lang.StringBuilder 14 .6 . Методы первого порядка класса List 313 Есть также метод copyToArray , который копирует элементы списка в после довательные позиции массива внутри некоего результирующего массива. Операция xs.copyToArray(arr, start) копирует все элементы списка xs в массив arr , начиная с позиции start Нужно обеспечить достаточную длину результирующего массива arr , чтобы в нем мог поместиться весь список. Рассмотрим пример: val arr2 = new Array[Int](10) // Array(0, 0, 0, 0, 0, 0, 0, 0, 0, 0) List(1, 2, 3).copyToArray(arr2, 3) arr2 // Array(0, 0, 0, 1, 2, 3, 0, 0, 0, 0) И наконец, если нужно получить доступ к элементам списка через итератор, то можно воспользоваться методом iterator : val it = abcde.iterator it.next() // a it.next() // b Пример: сортировка слиянием Ранее представленная сортировка вставками записывается кратко, но эф фективность ее невысока. Ее усредненная вычислительная сложность про порциональна квадрату длины входного списка. Более эффективен алгоритм сортировки слиянием. УСКОРЕННЫЙ РЕЖИМ ЧТЕНИЯ Этот пример — еще одна иллюстрация карринга и принципа «разделяй и властвуй» . Кроме того, в нем говорится о вычислительной сложности алгоритма, что может оказаться полезным . Если же вы хотите поскорее перейти к практике, то раздел 14 .7 можно спокойно пропустить . Сортировка слиянием работает следующим образом: если список имеет один элемент или не имеет никаких элементов, то он уже отсортирован, поэтому может быть возвращен в исходном виде. Более длинные списки разбива ются на два подсписка, в каждом из которых содержится около половины элементов исходного списка. Каждый подсписок сортируется с помощью рекурсивного вызова функции sort , затем два отсортированных списка объ единяются в ходе операции слияния. 314 Глава 14 • Работа со списками Чтобы выполнить обобщенную реализацию сортировки слиянием, вам при дется оставить публичными тип элементов сортируемого списка и функ цию, которая будет использоваться для сравнения элементов. Максимально обобщенную функцию можно получить, передав ей эти два элемента в ка честве параметров. При этом получится реализация, показанная в листин ге 14.2. Листинг 14.2. Функция сортировки слиянием объектов List def msort[T](less: (T, T) => Boolean) (xs: List[T]): List[T] = def merge(xs: List[T], ys: List[T]): List[T] = (xs, ys) match case (Nil, _) => ys case (_, Nil) => xs case (x :: xs1, y :: ys1) => if less(x, y) then x :: merge(xs1, ys) else y :: merge(xs, ys1) val n = xs.length / 2 if n == 0 then xs else val (ys, zs) = xs.splitAt(n) merge(msort(less)(ys), msort(less)(zs)) Вычислительная сложность msort — n log (n), где n — длина входного спи ска. Чтобы понять причину происходящего, следует отметить: и разбиение списка на два подсписка, и слияние двух отсортированных списков требу ют времени, которое пропорционально длине аргумента list(s) . Каждый рекурсивный вызов msort вполовину уменьшает количество элементов, используемых им в качестве входных данных. Поэтому производится при мерно log (n) последовательных вызовов, выполняемых до тех пор, пока не будет достигнут базовый вариант для списков длиной в единицу. Но для более длинных списков каждый вызов порождает два последующих вызова. Если все это сложить вместе, получится, что на каждом уровне вызова log (n) каждый элемент исходных списков примет участие в одной операции раз биения и одной операции слияния. Следовательно, каждый уровень вызова имеет общий уровень затрат, про порциональный n. Поскольку число уровней вызова равно log (n), мы полу чаем общий уровень затрат, пропорциональный n log (n). Он не зависит от исходного распределения элементов в списке, следовательно, в наихудшем варианте будет таким же, как уровень затрат в усредненном. Это свойство делает сортировку слиянием весьма привлекательным алгоритмом для сор тировки списков. 14 .7 . Методы высшего порядка класса List 315 Пример использования msort выглядит следующим образом: msort((x: Int, y: Int) => x < y)(List(5, 7, 1, 3)) // List(1, 3, 5, 7) Функция msort представляет собой классический образец карринга, рас смотренный в разделе 9.3. Карринг упрощает специализацию функции для конкретных функций сравнения. Рассмотрим пример: val intSort = msort((x: Int, y: Int) => x < y) // intSort имеет тип List[Int] => List[Int] Переменная intSort ссылается на функцию, которая получает список цело численных значений и сортирует их в порядке следования чисел. Как объяс нялось в разделе 8.6, в этом примере msort применяется частично, поскольку в нем отсутствует список аргументов. В данном случае в качестве недоста ющего аргумента фигурирует список, который должен быть отсортирован. А вот другой пример, который демонстрирует способ возможного определе ния функции, выполняющей сортировку списка целочисленных значений в обратном порядке следования чисел: val reverseIntSort = msort((x: Int, y: Int) => x > y) Поскольку функция сравнения уже представлена с помощью карринга, при вызове функций intSort или reverseIntSort нужно будет только предоста вить сортируемый список. Рассмотрим несколько примеров: val mixedInts = List(4, 1, 9, 0, 5, 8, 3, 6, 2, 7) intSort(mixedInts) // List(0, 1, 2, 3, 4, 5, 6, 7, 8, 9) reverseIntSort(mixedInts) // List(9, 8, 7, 6, 5, 4, 3, 2, 1, 0) 14 .7 . Методы высшего порядка класса List У многих операций над списками схожая структура. Раз за разом исполь зуется несколько схем. К подобным примерам можно отнести какоелибо преобразование каждого элемента списка; проверку того, что свойство соблюдается для всех элементов списка; извлечение из списка элементов, удовлетворяющих неким критериям; или объединение элементов списка с помощью того или иного оператора. В императивных языках подобные схемы традиционно будут создаваться идиоматическими комбинациями циклов for или while . В Scala они могут быть выражены более коротко 316 Глава 14 • Работа со списками и непосредственно за счет использования операторов высшего порядка 1 , которые реализуются в виде методов, определенных в классе List . Этим операторам высшего порядка и посвящен данный раздел. Отображения списков: map, flatMap и foreach Операция xs map f получает в качестве операндов список xs типа List[T] и функцию f типа T => U . Она возвращает список, получающийся в результате применения f к каждому элементу списка xs , например: List(1, 2, 3).map(_ + 1) // List(2, 3, 4) val words = List("the", "quick", "brown", "fox") words.map(_.length) // List(3, 5, 5, 3) words.map(_.toList.reverse.mkString) // List(eht, kciuq, nworb, xof) Оператор flatMap похож на map , но в качестве правого операнда получа ет функцию, возвращающую список элементов. Он применяет функцию к каждому элементу списка и возвращает конкатенацию всех результатов выполнения функции. Разница между map и flatMap показана в следующем примере: words.map(_.toList) // List(List(t, h, e), List(q, u, i, c, k), // List(b, r, o, w, n), List(f, o, x)) words.flatMap(_.toList) // List(t, h, e, q, u, i, c, k, b, r, o, w, n, f, o, x) Как видите, там, где map возвращает список списков, flatMap возвращает единый список, в котором все элементы списков сконкатенированы. Различия и взаимодействие методов map и flatMap показаны также следу ющим выражением, с помощью которого создается список всех пар (i, j) , отвечающих условию 1 ≤ j < i < 5 : List.range(1, 5).flatMap( i => List.range(1, i).map(j => (i, j)) ) // List((2,1), (3,1), (3,2), (4,1), // (4,2), (4,3)) 1 Под операторами высшего порядка понимаются функции высшего порядка, ис пользуемые в системе записи операторов. Как упоминалось в разделе 9.1, функция является функцией высшего порядка, если получает в качестве параметров одну функцию и более. 14 .7 . Методы высшего порядка класса List 317 Метод List.range является вспомогательным, создающим список из всех целых чисел в некотором диапазоне. В этом примере он используется дважды в целях создания списков целых чисел: в первый раз — списка целых чисел от 1 (включительно) до 5 (не включительно), во второй — списка целых чисел от 1 до i для каждого значения i , взятого из первого списка. Метод map в данном выражении создает список кортежей (i, j) , где j < i . Внешний метод flatMap в этом примере создает данный список для каждого i между 1 и 5 , а затем конкатенирует все результаты. Подругому этот же список может быть создан с помощью выражения for : for i <- List.range(1, 5); j <- List.range(1, i) yield (i, j) Третья map подобная операция — foreach . Но в отличие от map и flatMap она получает в качестве правого операнда процедуру (функцию, результи рующим типом которой является Unit ). Она просто применяет процедуру к каждому элементу списка. А сам результат операции также имеет тип Unit , то есть никакого результирующего списка не будет. В качестве примера рас смотрим краткий способ суммирования всех чисел списка: scala> var sum = 0 var sum: Int = 0 scala> List(1, 2, 3, 4, 5).foreach(sum += _) scala> sum val res39: Int = 15 Фильтрация списков: filter, partition, find, takeWhile, dropWhile и span Операция xs filter p получает в качестве операндов список xs типа List[T] и функциюпредикат p типа T => Boolean . Эта операция выдает список всех элементов x из списка xs , для которых p(x) вычисляется в true , например: List(1, 2, 3, 4, 5).filter(_ % 2 == 0) // List(2, 4) words.filter(_.length == 3) // List(the, fox) Метод partition похож на метод filter , но возвращает пару списков. Один список содержит все элементы, для которых предикат вычисляется в true , а другой — все элементы, для которых предикат вычисляется в false Он определяется равенством xs.partition(p) равно (xs.filter(p), xs.filter(!p(_))) 318 Глава 14 • Работа со списками Пример его работы выглядит следующим образом: List(1, 2, 3, 4, 5).partition(_ % 2 == 0) // (List(2, 4),List(1, 3, 5)) Метод find тоже похож на метод filter , но возвращает только первый эле мент, который удовлетворяет условию заданного предиката, а не все такие элементы. Операция xs find p получает в качестве операндов список xs и предикат p . Она возвращает Option . Если в списке xs есть элемент x , для которого p(x) вычисляется в true , то возвращается Some(x) . В противном случае p вычисляется в false для всех элементов и возвращается None . Вот несколько примеров работы этого метода: List(1, 2, 3, 4, 5).find(_ % 2 == 0) // Some(2) List(1, 2, 3, 4, 5).find(_ <= 0) // None Операторы takeWhile и dropWhile также получают в качестве правого операн да предикат. Операция xs.takeWhile(p) получает самый длинный префикс списка xs , в котором каждый элемент удовлетворяет условию предиката p Аналогично этому операция xs.dropWhile(p) удаляет самый длинный пре фикс из списка xs , в котором каждый элемент удовлетворяет условию пре диката p . Ряд примеров использования этих методов выглядит следующим образом: List(1, 2, 3, -4, 5).takeWhile(_ > 0) // List(1, 2, 3) words.dropWhile(_.startsWith("t")) // List(quick, brown, fox) Метод span объединяет takeWhile и dropWhile в одну операцию точно так же, как метод splitAt объединяет stake и drop . Он возвращает пару из двух списков, определяемых следующим равенством: xs span p равно (xs takeWhile p, xs dropWhile p) Как и splitAt , метод span избегает двойного прохода элементов списка: List(1, 2, 3, -4, 5).span(_ > 0) // (List(1, 2, 3),List(-4, 5)) Применение предикатов к спискам: forall и exists Операция xs.forall(p) получает в качестве аргументов список xs и преди кат p . Она возвращает результат true , если все элементы списка удовлетво ряют условию предиката p . Напротив, операция xs exists p возвращает true , если в xs есть хотя бы один элемент, удовлетворяющий условию предиката p 14 .7 . Методы высшего порядка класса List 319 Например, чтобы определить наличие в матрице, представленной списком списков, строки, состоящей только из нулевых элементов, можно применить следующий код: def hasZeroRow(m: List[List[Int]]) = m.exists(row => row.forall(_ == 0)) hasZeroRow(diag3) // false Свертка списков: foldLeft и foldRight Еще один распространенный вид операции объединяет элементы списка с помощью оператора, например: sum(List(a, b, c)) равно 0 + a + b + c Это особый случай операции свертки: def sum(xs: List[Int]): Int = xs.foldLeft(0)(_ + _) Аналогично этому product(List(a, b, c)) равно 1 * a * b * c представляет собой особый случай этой операции свертки: def product(xs: List[Int]): Int = xs.foldLeft(1)(_ * _) Операция левой свертки xs.foldLeft(z)(op) задействует три объекта: на чальное значение z , список xs и бинарную операцию op . Результат свертки — применение op между последовательно извлекаемыми элементами списка, где в качестве префикса выступает значение z , например: List(a, b, c).foldLeft(z)(op) равно op(op(op(z, a), b), c) Или в графическом представлении: Вот еще один пример, иллюстрирующий использование операции foldLeft Чтобы объединить все слова в списке из строковых значений с пробелами 320 Глава 14 • Работа со списками между ними и пробелом в самом начале списка, можно задействовать сле дующий код: words.foldLeft("")(_ + " " + _) // " the quick brown fox" Этот код выдаст лишний пробел в самом начале. Избавиться от него можно с помощью слегка видоизмененного варианта кода: words.tail.foldLeft(words.head)(_ + " " + _) // "the quick brown fox" Операция foldLeft создает деревья операций с уклоном влево. По аналогии с этим оператор foldRight создает деревья операций с уклоном вправо, на пример: List(a, b, c).foldRight(z)(op) равно op(a, op(b, op(c, z))) Или в графическом представлении: Для ассоциативных операций левая и правая свертки абсолютно эквивалент ны, но эффективность их применения может существенно различаться. Рас смотрим, к примеру, операцию, соответствующую методу flatten , которая конкатенирует все элементы в список списков. Она может быть реализована с помощью либо левой, либо правой свертки: def flattenLeft[T](xss: List[List[T]]) = xss.foldLeft(List[T]())(_ ::: _) def flattenRight[T](xss: List[List[T]]) = xss.foldRight(List[T]())(_ ::: _) Поскольку конкатенация списков xs ::: ys занимает время, пропорциональ ное длине его первого аргумента xs , то реализация в понятиях правой сверт ки в flattenRight более эффективна, чем реализация с применением левой свертки в flattenLeft . Дело в том, что flattenLeft(xss) копирует первый элемент списка xss.head n – 1 раз, где n — длина списка xss Учтите, что обе версии flatten требуют аннотации типа в отношении пу стого списка, который является начальным значением свертки. Это связано 14 .7 . Методы высшего порядка класса List 321 с ограничениями в имеющемся в Scala механизме вывода типов, который не в состоянии автоматически вывести правильный тип списка. При попытке игнорировать аннотацию будет выдано такое сообщение об ошибке: scala> def flattenRight[T](xss: List[List[T]]) = xss.foldRight(List())(_ ::: _) 2 | xss.foldRight(List())(_ ::: _) | ˆ | Found: (_$1 : List[T]) | Required: List[Nothing] Чтобы понять, почему не был выполнен надлежащий вывод типа, нужно узнать о типах методов свертки и способах их реализации. Более подробно этот вопрос рассматривается в разделе 14.10. Пример: реверсирование списков с помощью свертки Ранее в этой главе была показана реализация метода реверсирования по имени rev , время работы которой имело квадратичную вычислительную сложность по длине реверсируемого списка. Теперь будет показана другая реализация метода реверсирования с линейной вычислительной сложно стью. Идея состоит в том, чтобы воспользоваться операцией левой свертки, основанной на следующей схеме: def reverseLeft[T](xs: List[T]) = xs.foldLeft(стартовое_значение)(операция) Остается заполнить части стартовое_значение и операция . Собственно, вы можете попытаться вывести эти части из нескольких простых примеров. Чтобы правильно вывести стартовое_значение , можно начать с наименьшего потенциального списка, List() и рассуждать следующим образом: List() равен (в понятиях свойств reverseLeft) reverseLeft(List()) равен (по схеме для reverseLeft) List().foldLeft(стартовое_значение)(операция) равен (по определению foldLeft) стартовое_значение |