Scala. Профессиональное программирование 2022. Одерски Мартин, Спун Лекс, Веннерс Билл, Соммерс ФрэнкО41 Scala. Профессиональное программирование. 5е изд спб. Питер, 2022. 608 с. ил. Серия Библиотека программиста
 Скачать 6.24 Mb.
|
|
Листинг 13.19. Отбор элементов списка, соответствующих паттерну val results = List(Some("apple"), None, Some("orange")) for Some(fruit) <- results yield fruit // List(apple, orange) 13 .8 . Большой пример 291 В этом примере показано, что сгенерированные значения, не соответству ющие паттерну, отбрасываются. Так, второй элемент None в получившемся списке не соответствует паттерну Some(fruit) , поэтому отсутствует в ре зультате. 13 .8 . Большой пример После изучения различных форм паттернов может быть интересно посмо треть на их применение в более существенном примере. Предлагаемая задача заключается в написании класса, форматирующего выражения, который вы водит арифметическое выражение в двумерной разметке. Такое выражение деления, как x / (x + 1) , должно быть выведено вертикально — с числителем, показанным над знаменателем: x ----- x + 1 В качестве еще одного примера ниже в двумерной разметке показано вы ражение ((a / (b * c) + 1 / n) / 3) : a 1 ----- + - b * c n --------- 3 Исходя из этих примеров, можно прийти к выводу, что манипулированием разметкой должен заняться класс — назовем его ExprFormatter , поэтому имеет смысл задействовать библиотеку разметки, разработанную в главе 10. Мы также используем семейство case классов Expr , ранее уже встречавшееся в данной главе, и поместим в именованные пакеты как библиотеку разметки из главы 10, так и средство форматирования выражений. Полный код этого примера будет показан ниже, в листингах 13.20 и 13.21. Сначала полезно будет сосредоточиться на горизонтальной разметке. Струк турированное выражение BinOp("+", BinOp("*", BinOp("+", Var("x"), Var("y")), Var("z")), Num(1)) 292 Глава 13 • Сопоставление с образцом должно привести к выводу (x + y) * z + 1 . Обратите внимание на обязатель ность круглых скобок вокруг выражения x + y и их необязательность вокруг выражения (x + y) * z . Чтобы разметка получилась максимально разборчи вой, следует стремиться к отказу от избыточных круглых скобок и обеспе чить наличие всех обязательных. Чтобы узнать, куда ставить круглые скобки, код должен быть в курсе от носительной приоритетности каждого оператора; как следствие, неплохо было бы сначала отрегулировать именно этот вопрос. Относительную прио ритетность можно выразить непосредственно в виде литерала отображения следующей формы: Map( "|" –> 0, "||" –> 0, "&" –> 1, "&&" –> 1, ... ) Конечно, вам потребуется предварительно выполнить определенный объем вычислительной работы для назначения приоритетов. Удобнее будет просто определить группы операторов с нарастающим уровнем приоритета, а затем, исходя из этого, вычислить приоритет каждого оператора. Соответствующий код показан в листинге 13.20. Листинг 13.20. Верхняя половина средства форматирования выражений package org.stairwaybook.expr import org.stairwaybook.layout.Element.elem sealed abstract class Expr case class Var(name: String) extends Expr case class Num(number: Double) extends Expr case class UnOp(operator: String, arg: Expr) extends Expr case class BinOp(operator: String, left: Expr, right: Expr) extends Expr class ExprFormatter: // Содержит операторы в группах с нарастающей степенью приоритетности private val opGroups = Vector( Set("|", "||"), Set("&", "&&"), Set("ˆ"), Set("==", "!="), Set("<", "<=", ">", ">="), Set("+", "-"), Set("*", "%") ) 13 .8 . Большой пример 293 // Отображение операторов на их степень приоритетности private val precedence = { val assocs = for i <- 0 until opGroups.length op <- opGroups(i) yield op –> i assocs.toMap } private val unaryPrecedence = opGroups.length private val fractionPrecedence = -1 // продолжение в листинге 13.21... Переменная precedence — отображение операторов на уровень их приорите та, представленный целыми числами, начинающимися с нуля. Приоритет вы числяется с использованием выражения for с двумя генераторами. Первый выдает каждый индекс i вектора opGroups , второй — каждый оператор op , находящийся в opGroups(i) . Для каждого такого оператора выражение for выдает привязку оператора op к его индексу i . В результате приоритетность оператора берется из его относительной позиции в векторе. Листинг 13.21. Нижняя половина средства форматирования выражений // ...продолжение, начало в листинге 13.20 import org.stairwaybook.layout.Element private def format(e: Expr, enclPrec: Int): Element = e match case Var(name) => elem(name) case Num(number) => def stripDot(s: String) = if s endsWith ".0" then s.substring(0, s.length - 2) else s elem(stripDot(number.toString)) case UnOp(op, arg) => elem(op) beside format(arg, unaryPrecedence) case BinOp("/", left, right) => val top = format(left, fractionPrecedence) val bot = format(right, fractionPrecedence) val line = elem('-', top.width.max(bot.width), 1) val frac = top above line above bot if enclPrec != fractionPrecedence then frac 294 Глава 13 • Сопоставление с образцом else elem(" ") beside frac beside elem(" ") case BinOp(op, left, right) => val opPrec = precedence(op) val l = format(left, opPrec) val r = format(right, opPrec + 1) val oper = l beside elem(" " + op + " ") beside r if enclPrec <= opPrec then oper else elem("(") beside oper beside elem(")") end match def format(e: Expr): Element = format(e, 0) end ExprFormatter Привязки записываются с помощью инфиксной стрелки, например op –> i До сих пор они были показаны только как часть конструкций отображений, но и сами по себе они имеют значение. Фактически привязка op –> i есть не что иное, как пара (op, i) Теперь, зафиксировав уровень приоритета всех бинарных операторов, за исключением / , имеет смысл обобщить данную концепцию, охватив также унарные операторы. Уровень приоритета унарного оператора выше, чем у любого бинарного оператора. Поэтому для переменной unaryPrecedence , показанной в листинге 13.20, устанавливается значение длины вектора opGroups на единицу большее, чем уровень приоритета операторов * и % Прио ритет оператора деления рассматривается не так, как у других опе раторов, поскольку для дробей используется вертикальная разметка. Но, конечно же, было бы удобно присвоить оператору деления специальное значение уровня приоритета -1 , поэтому переменная fractionPrecedence будет инициализирована значением -1 , как было показано в листинге 13.20. После такой подготовительной работы можно приступать к написанию основного метода format . Этот метод получает два аргумента: выражение e , имеющее тип Expr , и уровень приоритета enclPrec того оператора, который непосредственно заключен в данное выражение. (Если в выражении нет ни какого оператора, то значение enclPrec должно быть нулевым.) Метод выда ет элемент разметки, представленный в виде двумерного массива символов. В листинге 13.21 показана остальная часть класса ExprFormatter , включа ющая два метода. Первый — приватный метод format — выполняет основную работу по форматированию выражений. Второй, который также называется format , представляет собой единственный публичный метод в библиотеке, получающий выражение для форматирования. Приватный метод format 13 .8 . Большой пример 295 проделывает свою работу, выполняя сопоставление с образцом по разно видностям выражения. У выражения match есть пять вариантов, каждый из которых будет рассмотрен отдельно. Первый вариант имеет следующий вид: case Var(name) => elem(name) Если выражение является переменной, то результатом станет элемент, сфор мированный из имени переменной. Второй вариант выглядит так: case Num(number) => def stripDot(s: String) = if s endsWith ".0" then s.substring(0, s.length - 2) else s elem(stripDot(number.toString)) Если выражение является числом, то результатом станет элемент, сформи рованный из значения числа. Функция stripDot очистит изображение числа с плавающей точкой, удалив из строки любой суффикс вида ".0" А вот как выглядит третий вариант: case UnOp(op, arg) => elem(op) beside format(arg, unaryPrecedence) Если выражение представляет собой унарную операцию UnOp(op, arg) , то результат будет сформирован из операции op и результата форматирования аргумента arg с самым высоким из возможных уровнем приоритета, име ющимся в данном окружении 1 . Это означает, что, если аргумент arg является бинарной операцией (но не делением), то всегда будет отображаться в круг лых скобках. Четвертый вариант представлен следующим кодом: case BinOp("/", left, right) => val top = format(left, fractionPrecedence) val bot = format(right, fractionPrecedence) val line = elem('-', top.width.max(bot.width), 1) val frac = top above line above bot 1 Значение unaryPrecedence является самым высоким из возможных приоритетом, поскольку ему было присвоено значение, на единицу превышающее значения прио ритета операторов * и % 296 Глава 13 • Сопоставление с образцом if enclPrec != fractionPrecedence then frac else elem(" ") beside frac beside elem(" ") Если выражение имеет вид дроби, то промежуточный результат frac фор мируется путем помещения отформатированных операндов left и right друг над другом с разделительным элементом в виде горизонтальной линии. Ширина горизонтальной линии равна максимальной ширине отформатиро ванных операндов. Промежуточный результат становится окончательным, если только дробь сама по себе не появляется в виде аргумента еще одной функции. В последнем случае по обе стороны frac добавляется по пробелу. Чтобы понять, зачем это делается, рассмотрим выражение (a / b) / c Без коррекции по ширине при форматировании этого выражения получится следующая картинка: a - b - c Вполне очевидна проблема с разметкой: непонятно, где именно находится дробная черта верхнего уровня. Показанное ранее выражение может означать либо (a / b) / c , либо a / (b / c) . Чтобы устранить неоднозначность, с обеих сторон разметки вложенной дроби a / b нужно добавить пробелы. Тогда разметка станет однозначной: a - b --- c Пятый и последний вариант выглядит следующим образом: case BinOp(op, left, right) => val opPrec = precedence(op) val l = format(left, opPrec) val r = format(right, opPrec + 1) val oper = l beside elem(" " + op + " ") beside r if enclPrec <= opPrec then oper else elem("(") beside oper beside elem(")") Этот вариант применяется ко всем остальным бинарным операциям. Он указан после варианта, который начинается со следующего кода: case BinOp("/", left, right) => ... 13 .8 . Большой пример 297 поэтому понятно, что оператор op в паттерне BinOp(op, left, right) не может быть оператором деления. Чтобы форматировать такую бинарную операцию, вам нужно сначала отформатировать его операнды left и right . В качестве параметра уровня приоритета для форматирования левого операнда ис пользуется opPrec оператора op , а для правого операнда берется уровень на единицу больше. Вдобавок такая схема обеспечивает правильную ассоциа тивность, выраженную круглыми скобками. Например, операция BinOp("-", Var("a"), BinOp("-", Var("b"), Var("c"))) будет вполне корректно выражена с применением круглых скобок в виде a - (b - c) . Затем с помощью выстраивания в линию операндов left и right , разделенных оператором, формируется промежуточный результат oper . Если уровень приоритета текущего оператора ниже уровня приоритета операто ра, заключенного в скобки, то oper помещается между круглыми скобками, в противном случае возвращается в исходном виде. На этом разработка приватной функции format завершена. Остается только пуб личный метод format , который позволяет программистам, создающим клиентский код, форматировать высокоуровневые выражения, не прибегая к передаче аргумента, содержащего уровень приоритета. Демонстрационная программа, с помощью которой проверяется ExprFormatter , показана в ли стинге 13.22. Листинг 13.22. Приложение, выполняющее вывод отформатированных выражений import org.stairwaybook.expr.* object Express: def main(args: Array[String]): Unit = val f = new ExprFormatter val e1 = BinOp("*", BinOp("/", Num(1), Num(2)), BinOp("+", Var("x"), Num(1))) val e2 = BinOp("+", BinOp("/", Var("x"), Num(2)), BinOp("/", Num(1.5), Var("x"))) val e3 = BinOp("/", e1, e2) def show(e: Expr) = println(s"${f.format(e)}\n\n") for e <- Vector(e1, e2, e3) do show(e) 298 Глава 13 • Сопоставление с образцом Поскольку этот объект определяет метод main , он является работоспособным приложением. Запустить программу Express можно командой scala Express При этом будет получен следующий вывод: 1 - * (x + 1) 2 x 1.5 - + --- 2 x 1 - * (x + 1) 2 ----------- x 1.5 - + --- 2 x Резюме В этой главе мы представили подробную информацию о case классах и со поставлении с образцом. Они позволяют получить преимущества в процессе использования ряда лаконичных идиом, которые обычно недоступны в объ ектноориентированных языках. Но реализованное в Scala сопоставление с образцом не ограничивается тем, что было показано в данной главе. Если нужно задействовать сопоставление с образцом, но при этом нежелательно открывать доступ к вашим классам, как делается в case классах, то можно обратиться к экстракторам. В следующей главе мы рассмотрим списки. 14 Работа со списками Вероятно, наиболее востребованные структуры данных в программах на Scala — списки. В этой главе мы подробно разъясним, что это такое. В ней мы представим много общих операций, которые могут выполняться над списками. Кроме того, раскроем некоторые наиболее важные принципы проектирования программ, работающих со списками. 14 .1 . Литералы списков Списки уже попадались в предыдущих главах, следовательно, вам извест но, что список, содержащий элементы 'a', 'b' и 'c' , записывается как List('a', 'b', 'c') . А вот другие примеры: val fruit = List("apples", "oranges", "pears") val nums = List(1, 2, 3, 4) val diag3 = List( List(1, 0, 0), List(0, 1, 0), List(0, 0, 1) ) val empty = List() Списки очень похожи на массивы, но имеют два важных отличия. Во первых, списки являются неизменяемой структурой данных, то есть их элементы нельзя изменить путем присваивания. Вовторых, списки имеют рекурсивную структуру (имеется в виду связанный список), а у массивов она линейная. 300 Глава 14 • Работа со списками 14 .2 . Тип List Как и массивы, списки однородны: у всех элементов списка один и тот же тип. Тип списка, имеющего элементы типа T , записывается как List[T] . На пример, далее показаны те же четыре списка, что и выше, с явным указанием типов: val fruit: List[String] = List("apples", "oranges", "pears") val nums: List[Int] = List(1, 2, 3, 4) val diag3: List[List[Int]] = List( List(1, 0, 0), List(0, 1, 0), List(0, 0, 1) ) val empty: List[Nothing] = List() В Scala тип списка обладает ковариантностью. Этот значит, что для каждой пары типов S и T , если S — подтип T , то List[S] — подтип List[T] . Например, List[String] — подтип List[Object] . И это вполне естественно, поскольку каждый список строк также может рассматриваться как список объектов 1 Обратите внимание: типом пустого списка является List[Nothing] No- thing считается «низшим типом» в иерархии классов Scala, так как он явля ется подтипом любого другого имеющегося в Scala типа. Списки ковариант ны, отсюда следует, что List[Nothing] — подтип List[T] для любого типа T Следовательно, пустой списочный объект, имеющий тип List[Nothing] , также может рассматриваться в качестве объекта любого другого списочного типа, имеющего вид List[T] . Именно поэтому вполне допустимо написать такой код: // List() также относится к типу List[String]! val xs: List[String] = List() 14 .3 . Создание списков Все списки создаются из двух основных строительных блоков: Nil и :: (про износится как «конс», от слова «конструировать»). Nil представляет собой пустой список. Инфиксный оператор конструирования :: обозначает рас ширение списка с начала. То есть запись x :: xs представляет собой список, первым элементом которого является x , за которым следует список xs (его 1 Более подробно ковариантность и другие разновидности вариантности рассмотре ны в главе 18. 14 .4 . Основные операции над списками 301 элементы). Следовательно, предыдущие списочные значения можно опре делить так: val fruit = "apples" :: ("oranges" :: ("pears" :: Nil)) val nums = 1 :: (2 :: (3 :: (4 :: Nil))) val diag3 = (1 :: (0 :: (0 :: Nil))) :: (0 :: (1 :: (0 :: Nil))) :: (0 :: (0 :: (1 :: Nil))) :: Nil val empty = Nil Фактически предыдущие определения fruit , nums , diag3 и empty , выражен ные в виде List(...) , всего лишь оболочки, которые разворачиваются в эти определения. Например, применение List(1, 2, 3) приводит к созданию списка 1 :: (2 :: (3 :: Nil)) То, что операция :: заканчивается двоеточием, означает ее правую ассоциа тивность: A :: B :: C интерпретируется как A :: (B :: C) . Поэтому круглые скобки в предыдущих определениях можно отбросить. Например val nums = 1 :: 2 :: 3 :: 4 :: Nil будет эквивалентом предыдущего определения nums 14 .4 . Основные операции над списками Все действия со списками можно свести к трем основным операциям: z z head возвращает первый элемент списка; z z tail возвращает список, состоящий из всех элементов, за исключением первого; z z isEmpty возвращает true , если список пуст. Эти операции определены как методы класса List . Некоторые примеры их использования показаны в табл. 14.1. Методы head и tail определены только для непустых списков. Будучи примененными к пустому списку, они гене рируют исключение: scala> Nil.head java.util.NoSuchElementException: head of empty list В качестве примера того, как можно обрабатывать список, рассмотрим сор тировку элементов списка чисел в возрастающем порядке. Один из про стых способов выполнить эту задачу заключается в сортировке вставками, |