Scala в примерах: различия между версиями

137 байт добавлено ,  6 лет назад
Категория:Scala плюс викификация
(Категория:Scala плюс викификация)
''Здесь ведется перевод книги Martin'аMartin’а Odersky [http://www.scala-lang.org/docu/files/ScalaByExample.pdf Scala by examples], которая описывает основные приемы программирования на языке [[w:Scala (язык программирования)|Scala<small><sup>↑</sup></small>]]. Присоединяйтесь!''
 
{{TOC right}}
Главы [[Scala в примерах#Первый пример|2]] и [[Scala в примерах#Программирование с акторами и сообщениями|3]] обращают внимание на некоторые возможности, из-за которых Scala особенно интересен. Последующие главы представляют конструкты языка более подробно, начиная с простых выражений и функций, через объекты и классы, списки и потоки, изменяемые состояния, сопоставление с образцом, к более сложным примерам, иллюстрирующим интересные приемы программирования. Это неформальное изложение должно быть дополнено документом [http://www.scala-lang.org/docu/files/ScalaReference.pdf Scala Language Reference Manual], который специфицирует Scala более точно и детально.
 
'''Замечание.''' Мы в огромном долгу у чудесной книги Абельсона и Сассмана, "«Структура и интерпретация компьютерных программ"». Многие примеры и упражнения оттуда также приведены здесь. Конечно, рабочий язык в каждом случае был изменен с Scheme на Scala. Кроме того, в примерах использованы объектно-ориентированные конструкты Scala, где это уместно.
 
= Первый пример =
Взглянув снова на первую, императивную реализацию быстрой сортировки, мы увидим там многие языковые конструкты из второго решения, хотя и в замаскированной форме.
 
Например, "«обычные"» бинарные операторы, такие как <tt>+</tt>,  <tt>-</tt> или <tt><</tt>, не рассматриваются специальным образом. Как и <tt>append</tt>, они являются методами своих левых операндов. Следовательно, выражение <tt>i + 1</tt> рассматривается как вызов <tt>i.+(1)</tt> метода <tt>+</tt> на целом числе. Конечно, компилятор может (если он достаточно умный) распознать специальный случай вызова метода <tt>+</tt> на целочисленных аргументах и сгенерировать эффективный встраиваемый код для него.
 
Для эффективности и лучшего обнаружения ошибок цикл '''<tt>while</tt>''' представлен в Scala как примитивная конструкция языка. Но, в принципе, его можно было бы вынести в библиотеку, оформив как функцию. Вот возможная реализация:
Функция <tt>While</tt> принимает первым параметром функцию проверки, которая не имеет аргументов, и возвращает булево значение. Второй параметр это командная функция, которая также не имеет аргументов и возвращает результат типа <tt>Unit</tt>. While вызывает командную функцию до тех пор, пока предикатная функция возвращает <tt>true</tt>.
 
Тип <tt>Unit</tt> в Scala, грубо говоря, соответствует <tt>void</tt> в Java; он используется всякий раз, когда функция не возвращает какого-либо интересного значения. На самом деле, поскольку Scala это язык, ориентированный на выражения, каждая функция возвращает некоторый результат. Если нет явно заданного выражения, то предполагается значение по умолчанию, <tt>()</tt> (произносится "«unit"»). Это значение имеет тип <tt>Unit</tt>. Функции, возвращающие <tt>Unit</tt>, также называются ''процедурами''. Вот более "«ориентированная на выражения"» формулировка функции swap из первой реализации быстрой сортировки, которая выражает это явно:
 
<div style="width: 450px"><font size="3">
= Программирование с акторами и сообщениями =
 
Вот пример, который демонстрирует область применения, для которой Scala особенно хорошо подходит. Рассмотрим задачу по созданию электронного аукциона. Для реализации участников аукциона мы используем модель акторных процессов в [http://erlang.org Erlang]-стиле. Акторы  — это объекты, которым посылаются сообщения. У каждого актора есть "«почтовый ящик"» для поступающих сообщений, который представлен очередью. Сообщения в очереди могут обрабатываться или в последовательном порядке, или выборочно, как удовлетворяющие некоторому образцу.
 
Для каждого лота есть актор-аукционщик, который публикует информацию о лоте, принимает предложения от участников и общается с продавцом лота и победившим покупателем для завершения сделки.
* Метод <tt>receiveWithin</tt> класса [http://www.daimi.au.dk/~eernst/dProgSprog06/share/doc/scala-1.4.0.4/api/scala/concurrent/Actor-class.html <tt>Actor</tt>] принимает в качестве параметров продолжительность торгов в миллисекундах и функцию, которая обрабатывает сообщения, поступающие в почтовый ящик. Функция задана последовательностью вариаций, каждая из которых определяет шаблон и действия, которые следует предпринять для сообщений, соответствующих этому шаблону. Метод <tt>receiveWithin</tt> выбирает из почтового ящика первое сообщение, которое соответствует одному из этих шаблонов и выполняет соответствующее действие.
 
* Последняя вариация в <tt>receiveWithin</tt>  — для шаблона <tt>TIMEOUT</tt>. Если никакие другие сообщения не были получены в последнее время, по истечении срока, который передается в <tt>receiveWithin</tt> как аргумент, срабатывает шаблон <tt>TIMEOUT</tt>. <tt>TIMEOUT</tt>  — это особое сообщение (экземпляр класса [http://www.daimi.au.dk/~eernst/dProgSprog06/share/doc/scala-1.4.0.4/api/scala/collection/mutable/Message-class.html <tt>Message</tt>]), которое посылается в реализации класса <tt>Actor</tt>.
 
* Ответные сообщения посылаются в форме <tt>destination ! SomeMessage</tt>. <tt>!</tt> используется здесь как бинарный оператор с аргументами: актором и сообщением. В Scala это равносильно вызову метода <tt>destination.!(SomeMessage)</tt>, т.е.то есть вызову метода <tt>!</tt> актора-реципиента с сообщением в качестве параметра.
 
Предыдущее обсуждение показало возможности распределенного программирования на Scala. Может показаться, что в Scala есть богатый набор языковых конструкций, поддерживающих процессы-акторы, обмен сообщениями, программирование с тайм-аутами, и  т. п. В действительности это не так. Все конструкции, рассмотренные выше, вводятся как методы в библиотечном классе <tt>Actor</tt>.
Сам класс написан на Scala и базируется на модели многопоточности, используемой в нижележащей платформе (напр. Java или .NET). Все возможности класса <tt>Actor</tt>, использованные здесь, рассмотрены в [[Scala в примерах#Акторы|Параграфе 17.11]].
 
Преимущество подобного библиотечного подхода к многопоточности ''(см. также [http://lamp.epfl.ch/~cremet/publications/pilib.pdf PiLib]) ''  — в относительной простоте основного языка и гибкости для разработчиков библиотек. Поскольку основному языку не нужно определять детали высокоуровневого обмена информацией между процессами, он может оставаться простым и более общим. Поскольку конкретная модель сообщений в почтовом ящике  — библиотечный модуль, она может свободно быть модифицирована, если это требуется в каких-то приложениях. Впрочем, для такого подхода необходимо, чтобы базовый язык был достаточно выразителен, чтобы он мог обеспечивать необходимые языковые абстракции удобным способом. Scala разработан с учетом этого требования; одна из основных целей при проектировании заключалась в том, чтобы сделать его достаточно гибким, чтобы он мог выступать удобной платформой для доменно-специфичных языков, реализованных как библиотечные модули. Например, представленные выше конструкции для коммуникации между акторами могут рассматриваться как доменно-специфичный язык, который, в принципе, расширяет ядро Scala.
 
= Выражения и простые функции =
== Выражения и простые функции ==
 
В дистрибутив Scala входит интерпретатор, который можно рассматривать как сложный калькулятор. Пользователь взаимодействует с калькулятором, вводя выражения. Калькулятор возвращает результаты вычислений и их типы. Например,
 
<font size=3><syntaxhighlight lang=Bash>
* применить оператор к значениям операндов.
 
Имя, определенное при помощи <tt>'''def'''</tt>, вычисляется путем замены имени на (невычисленную) правую часть определения. Имя, определенное при помощи <tt>'''val'''</tt>, вычисляется путем замены имени на значение правой части. Процесс вычисления заканчивается, когда приходит к одному значению. Значение  — это некоторые данные, как например: строка, число, массив или список.
 
'''Пример 4.1.1''' Здесь представлено вычисление арифметического выражения.
</syntaxhighlight></font>
 
Параметры функций перечисляются после имени функции и всегда заключаются в скобки. Каждый параметр имеет тип, который указывается после имени параметра и двоеточия. Пока что нам потребуются только базовые числовые типы, такие как <tt>scala.Double</tt>  — типа числа двойной точности. Scala определяет псевдонимы для некоторых стандартных типов, так что мы можем писать численные типы, как в Java. Например, псевдоним <tt>double</tt>  — <tt>scala.Double</tt>, а псевдоним <tt>int</tt>  — <tt>scala.Int</tt>.
 
Функции с параметрами вычисляются аналогично операторам в выражениях. Сначала вычисляются аргументы функции (слева направо). Затем применение функции заменяется на ее правую часть, и в то же время все формальные параметры функции заменяются на соответствующие им фактические аргументы.
== Условные выражения ==
 
<tt>'''if-else'''</tt> в Scala позволяет выбирать между двумя альтернативами. Синтаксис похож на <tt>'''if-else'''</tt> в Java. Но тогда как <tt>'''if-else'''</tt> в Java можно использовать только для альтернативных утверждений, Scala позволяет использовать тот же синтаксис для выбора между двумя выражениями. Поэтому в Scala <tt>'''if-else'''</tt> служит также для замены условного выражения Java <tt>… ? … : …</tt>.
 
'''Пример 4.3.2'''
== Пример: квадратные корни по методу Ньютона ==
 
Теперь проиллюстрируем элементы языка, которые мы упомянули к этому моменту, более интересной программой. Задание  — написать функцию
 
<font size=3><syntaxhighlight lang=Scala>
которая вычисляет квадратный корень <tt>x</tt>.
 
Обычный способ вычисления квадратных корней  — ньютоновский метод последовательных приближений. Мы начинаем с первой догадки <tt>y</tt> (скажем, <tt>y = 1</tt>). Затем будем улучшать текущую догадку <tt>y</tt>, вычисляя среднее между <tt>y</tt> и <tt>x/y</tt>. В качестве примера, следующие три столбца представляют догадку <tt>y</tt>, частное <tt>x/y</tt> и их среднее для первого приближения <math>\sqrt{2}</math>.
 
{| class="simple" border="0"
Между этими двумя последовательностями вывода есть важное различие: термы последовательности вывода <tt>gcd</tt> вновь и вновь принимают одну и ту же форму. В течение вычисления их длина ограничена константой. В вычислении факториала, напротив, мы получаем все более длинные цепи операндов, которые впоследствии перемножаются в последней части последовательности вычислений.
 
Несмотря на то, что на самом деле Scala не переписывает термы, затраты по памяти будут такими же, что и в последовательности вывода. Заметим, что в реализации <tt>gcd</tt> рекурсивный вызов <tt>gcd</tt>  — это последнее действие в теле вычисления. Это пример хвостовой рекурсии. Последний вызов в хвостово-рекурсивной функции может быть реализован прыжком обратно к началу этой функции. Аргументы такого вызова могут быть вписаны на место параметров текущего выполнения <tt>gcd</tt>, так что новой памяти на стеке выделять не нужно. Отметим, что хвостово-рекурсивные функции это итеративные процессы, которые могут выполняться в константной памяти.
 
Рекурсивый вызов <tt>factorial</tt>, напротив, заканчивается операцией умножения. Отметим, что для рекурсивного вызова <tt>factorial</tt> выделяется новый кадр стека, который стирается после завершения выполнения вызова. Данная реализации функции факториала не хвостово-рекурсивна, и ей необходимо количество памяти, пропорциональное размеру ввода.
'''Упражнение 4.6.1''' Придумайте хвостово-рекурсивную версию функции <tt>factorial</tt>.
 
= Функции первого класса =
 
Функции в Scala являются "«значениями первого класса"». Как любые другие значения, их можно передавать как параметры и возвращать как результаты. Функции, которые принимают другие функции в качестве параметров или возвращают их как результаты, называются ''функциями высшего порядка''. Эта глава представляет функции высшего порядка и показывает гибкий механизм для составления программ, которые они реализуют.
 
Для мотивации рассмотрим следующие три задания.
</syntaxhighlight></font>
 
3. Написать функцию для суммирования степеней двойки ''2<sup>n</sup>'' для всех целых чисел между двумя данными числами <tt>a</tt> и <tt>b</tt>:
 
<font size=3><syntaxhighlight lang=Scala>
</syntaxhighlight></font>
 
Тип <tt>Int => Int</tt>  — это тип функции, которая принимает аргумент типа <tt>Int</tt> и возвращает результат типа <tt>Int</tt>. Так что <tt>sum</tt>  — функция, берущая в качестве параметра другую функцию. Другими словами, <tt>sum</tt>  — функция высшего порядка.
 
Используя <tt>sum</tt>, мы можем сформулировать три суммирующие функции так:
</syntaxhighlight></font>
 
Часть перед стрелкой  — параметры функции, часть после нее  — тело функции. Вот, например, анонимная функция, перемножающая два аргумента:
 
<font size=3><syntaxhighlight lang=Scala>
</syntaxhighlight></font>
 
Выражение Scala <tt>(x<sub>1</sub>: T<sub>1</sub>, …, x<sub>n</sub>: T<sub>n</sub>) => E</tt> определяет функцию, которая соотносит свои параметры <tt>x<sub>1</sub>, …, x<sub>n</sub></tt> с результатами выражения <tt>E</tt> (где <tt>E</tt> может ссылаться на <tt>x<sub>1</sub>, …, x<sub>n</sub></tt>). Анонимные функции  — не основные элементы языка Scala, поскольку они всегда могут быть выражены через именованные функции. Действительно, анонимная функция
 
<code>
</code>
 
где <tt>f</tt>  — свежее имя, которое больше не используется нигде в программе. Можно сказать, что анонимные функции это "«синтаксический сахар"».
 
== Каррирование ==
</syntaxhighlight></font>
 
В этой формулировке <tt>sum</tt>  — это функция, которая возвращает другую функцию, а именно специализированную суммирующую функцию <tt>sumF</tt>. Эта последняя функция выполняет всю работу: она принимает границы <tt>a</tt> и <tt>b</tt> как параметры, применяет <tt>f</tt>, параметр <tt>sum</tt>, ко всем целым числам между ними, и суммирует результаты.
 
При помощи этой формулировки <tt>sum</tt> мы можем теперь определить:
функция <tt>sum</tt> применяется к функции возведения в квадрат <tt>(x => x * x)</tt>. Получившаяся функция затем применяется ко второму списку аргументов <tt>(1, 10)</tt>.
 
Такая запись возможна, потому что применение функций левоассоциативно. То есть, если args<sub>1</sub> и args<sub>2</sub>  — списки аргументов, то ''f''(args<sub>1</sub>)(args<sub>2</sub>) эквивалентно (''f''(args<sub>1</sub>))(args<sub>2</sub>).
 
В нашем примере <tt>sum(x => x * x)(1, 10)</tt> эквивалентно следующему выражению: <tt>(sum(x => x * x))(1, 10)</tt>.
</code>
 
где <tt>g</tt>  — свежий идентификатор. Или, если короче, с использованием анонимной фунции:
 
<code>
Такой стиль определения и применения функций называется ''каррирование'' (currying) в честь своего популяризатора Хаскелла Карри, логика XX века, хотя идея принадлежит Мозесу Шонфинкелю и Готтлобу Фреге.
 
Тип функции, возвращающей функцию, выражается аналогично списку ее параметров. Возьмем к примеру последнюю формулировку <tt>sum</tt>. Тип <tt>sum</tt>  — <tt>(Int => Int) => (Int, Int) => Int</tt>. Это возможно, потому что типы функций правоассоциативны. То есть, <tt>T1 => T2 => T3</tt> эквивалентно <tt>T1 => (T2 => T3)</tt>.
 
'''Упражнение 5.2.1''' 1. Функция <tt>sum</tt> использует линейную рекурсию. Напишите хвостоворекурсивный вариант, заполнив ??.
Теперь применим эту идею при формулировании функции вычисления квадратных корней. Начнем со спецификации <tt>sqrt</tt>: <tt> sqrt(x) = the ''y'' such that y * y = x = the ''y'' such that y = x / y</tt>.
 
Заметьте, что <tt>sqrt(x)</tt>  — неподвижная точка функции <tt>y => x / y</tt>. Поэтому <tt>sqrt(x)</tt> можно вычислить при помощи итерации неподвижной точки:
 
<font size=3><syntaxhighlight lang=Scala>
== Заключение ==
 
В предыдущей главе мы видели, что функции  — это очень важные абстракции, потому что они позволяют нам вводить общие методы вычислений как явные, именованные элементы нашего языка программирования. Настоящая глава показала, что эти абстракции могут быть скомбинированы при помощи функций высшего порядка, для создания дальнейших абстракций. Как программисты, мы должны искать возможности абстрагировать и переиспользовать. Самый высокий возможный уровень асбтракции не всегда самый лучший, но важно знать техники абстракции, чтобы уметь использовать их, где это уместно.
 
== Использованные элементы языка ==
<font size=3>'''Символы'''</font>
 
Программы Scala  — это последовательности символов Unicode. Мы различаем следующие множества символов:
* пробел, табуляция или символ перевода строки,
* буквы от ‘<tt>a</tt>’ до ‘<tt>z</tt>’, ‘<tt>A</tt>’ до ‘<tt>Z</tt>’,
| идентификатор '_' идентификатор
литерал = "как в Java"
</pre>
 
Литералы  — те же, что и в Java. Они определяют числа, символы, строки и булевские величины. Примеры литералов: <tt>0</tt>, <tt>1.0e10</tt>, <tt>'x'</tt>, <tt>"he said "hi!""</tt> или <tt>'''true'''</tt>.
 
Идентификаторы могут быть двух видов. Они начинаются либо с буквы, за которой идет (возможно, пустая) последовательность букв и символов, либо с операторного символа, за которым идет (возможно, пустая) последовательность операторных символов. Оба вида идентификаторов могут содержать символы подчеркивания. За символом подчеркивания могут идти идентификатры любого типа. Например, следующие идентификатры корректны: <tt>x&nbsp; Room10a&nbsp; +&nbsp; --&nbsp; foldl_:&nbsp; +_vector</tt>.
</syntaxhighlight></font>
 
Это определяет <tt>Rational</tt> как класс, принимающий два аргумента конструктора <tt>n</tt> и <tt>d</tt>, содержащие числитель и знаменатель числа. Класс предоставляет поля, возвращающие эти части, и методы для арифметических операций с рациональными числами. Левый операнд операции  — всегда рациональное число, для которого метод является членом (класса).
 
 
<font size=3>'''Наследование и переопределение'''</font>
 
У каждого класса в Scala есть предок в иерархии (суперкласс), который расширяется данным классом. Если класс не упоминает предка в своем определении, предком неявно предполагается корневой тип <tt>scala.AnyRef</tt> (для реализаций Java этот тип  — псевдоним <tt>java.lang.Object</tt>). Например, класс <tt>Rational</tt> можно эквивалентно определить так:
 
<font size=3><syntaxhighlight lang=Scala>
<font size=3>'''Методы без параметров'''</font>
 
В отличие от Java, методы в Scala не обязательно должны принимать список параметров. Пример тому  — метод <tt>square</tt>, представленный ниже. Этот метод вызывается просто упоминанием своего имени.
 
<font size=3><syntaxhighlight lang=Scala>
</syntaxhighlight></font>
 
И <tt>EmptySet</tt>, и <tt>NonEmptySet</tt> расширяют класс <tt>IntSet</tt>. Из этого следует, что типы <tt>EmptySet</tt> и <tt>NonEmptySet</tt> соответствуют типу <tt>IntSet</tt>  — значение типа <tt>EmptySet</tt> или <tt>NonEmptySet</tt> может быть использовано везде, где требуется значение типа <tt>IntSet</tt>.
 
'''Упражнение 6.0.1''' Напишите метод <tt>union</tt> и <tt>intersection</tt> для формирования объединения и пересечения двух множеств.
</syntaxhighlight></font>
 
Проблема этого подхода в том, что такое определение значения нелегально для высшего уровня в Scala, оно должно быть частью другогодрtt>xугого класса или объекта. К тому же определение класса <tt>EmptySet</tt> теперь выглядит несколько избыточным  — зачем определять класс объектов, если нам нужен только один объект этого класса? Более прямой подход  — использовать ''определение объекта''. Ниже представлен более прямолинейный вариант определения пустого множества:
 
<font size=3><syntaxhighlight lang=Scala>
<font size=3>'''Стандартные классы'''</font>
 
Scala  — чисто объектно-ориентированный язык. Это значит, что каждое значение в Scala может быть рассмотрено как объект. На самом деле даже примитивные типы, как <tt>int</tt> или <tt>boolean</tt>, не рассматриваются специально. Они определены как псевдонимы типов классов Scala в модуле <tt>Predef</tt>:
 
<font size=3><syntaxhighlight lang=Scala>
</syntaxhighlight></font>
 
Для эффективности компилятор обычно представляет значения типа <tt>scala.Int</tt> 32-битными целыми числами, значения <tt>scala.Boolean</tt>  — двоичными значениями Java, и  т. д. Но он преобразует эти специализированные представления в объекты, когда это требуется, например, когда значение примитивного типа <tt>Int</tt> передается в функцию с параметром типа <tt>AnyRef</tt>. Обратите внимание, что специальное представление примитивных значений это всего лишь оптимизация, оно не меняет смысла программы.
 
Вот спецификация класса <tt>Boolean</tt>:
</syntaxhighlight></font>
 
Класс <tt>Int</tt> можно в принципе реализовать, используя только объекты и классы, без ссылок на встроенный тип целых чисел. Чтобы понять, как это сделать, рассмотрим более простую задачу реализации типа <tt>Nat</tt> натуральных (т.е.то есть неотрицательных) чисел. Вот определение абстрактного класса <tt>Nat</tt>:
 
<font size=3><syntaxhighlight lang=Scala>
Впрочем, определять все эти методы в классах <tt>Number</tt> и <tt>Sum</tt> довольно утомительно. Более того, проблема становится еще хуже, если мы хотим добавить новые формы выражений. Например, рассмотрим добавление новой формы выражения <tt>Prod</tt> со всей предыдущей классификацией и методами доступа, мы также хотим ввести новый абстрактный метод <tt>isProduct</tt> в класс <tt>Expr</tt> и реализовать этот метод в подклассах <tt>Number</tt>, <tt>Sum</tt> и <tt>Prod</tt>. Необходимость модифицировать существующий код, когда система растет, всегда проблематично, поскольку это затрудняет контроль версий и поддержку.
 
Объектно-ориентированное программирование обещает, что такие модификации не обязательны, поскольку их можно избежать, переиспользуя существующий неизменяющийся код через механизм наследования. Действительно, более объектно-ориентированная организация решает проблему. Идея состоит в том, чтобы сделать операцию "«высшего уровня"» <tt>eval</tt> методом каждого класса выражений вместо того, чтобы реализовывать ее как функцию вне иерархии классов выражений, как мы делали прежде. Поскольку <tt>eval</tt> теперь  — метод всех классов выражений, классификация и методы доступа становятся излишними, и реализация сильно упрощается:
 
<font size=3><syntaxhighlight lang=Scala>
</syntaxhighlight></font>
 
Из этого примера мы можем сделать вывод, что объектно-ориентированная организация  — это лучшим подход для создания систем, которые должны быть расширяемы новыми типами данных. Но есть и другой способ, которым мы можем захотеть расширить пример с выражениями. Мы можем также захотеть добавить новые ''операции'' с выражениями. Например, добавить операцию, которая выводит на экран вывода дерево выражения.
 
Если мы определили классификацию и методы доступа, такую операцию можно легко написать в виде внешней функции. Вот пример:
== Case-классы и case-объекты ==
 
''Case-классы'' и ''case-объекты'' (вариации) определяются как обычные классы и объекты, за исключением того, что перед определением ставится модифиатор <tt>'''case'''</tt>. Например, определения
 
<font size=3><syntaxhighlight lang=Scala>
</syntaxhighlight></font>
 
2. У case-классов и case-объектов есть неявные реализации методов <tt>toString</tt>, <tt>equals</tt> и <tt>hashCode</tt>, которые переписывают одноименные методы класса <tt>AnyRef</tt>. Реализация этих методов принимает во внимание структуру членов case-класса в каждом случае. Метод <tt>toString</tt> представляет дерево выражения так, как оно было сконструировано. Поэтому
 
<font size=3><syntaxhighlight lang=Scala>
</syntaxhighlight></font>
 
который возвращает параметр конструктора <tt>n</tt>, а у <tt>Sum</tt>  — два метода
 
<font size=3><syntaxhighlight lang=Scala>
</syntaxhighlight></font>
 
Заметьте, что для значения <tt>s</tt> типа <tt>Sum</tt> теперь можно писать <tt>s.e1</tt> для доступа к левому операнду. Но для значения <tt>e</tt> типа <tt>Expr</tt> выражение <tt>e.e1</tt> будет некорректно, потому что <tt>e1</tt> определен в <tt>Sum</tt> и не является методом класса <tt>Expr</tt>. Итак, как определить конструктор и получить доступ к аргументам конструктора для значений, чей статический тип  — базовый класс <tt>Expr</tt>? Это решается четвертым и последним пунктом.
 
4. Сase-классы разрешают конструкцию ''образцов'' (patterns), которые относятся к конструкторам case-классов.
</syntaxhighlight></font>
 
В этом примере есть два случая. Каждый случай сопоставляет образец с выражением. Образцы сопоставляются со значениями селектора <tt>e</tt>. Первый образец в нашем примере, <tt>Number(n)</tt>, соответствует всем значениями вида <tt>Number(v)</tt>, где <tt>v</tt>  — произвольное значение. В этом случае ''переменная образца'' <tt>n</tt> связывается со значением <tt>v</tt>. Аналогично, образец <tt>Sum(l, r)</tt> соответствует всем значениям селектора вида <tt>Sum(v<sub>1</sub>, v<sub>2</sub>)</tt> и связывает переменные образца <tt>l</tt> и <tt>r</tt> с <tt>v<sub>1</sub></tt> и <tt>v<sub>2</sub></tt> соответственно.
 
В общем, образцы строятся из:
<font size=3>'''Анонимные функции сопоставления с образцом'''</font>
 
До этого case-выражения всегда появлялись вместе с оператором <tt>match</tt>. Но можно также использовать case-выражения сами по себе. Блок case-выражений, такой как
 
<code>
</code>
 
это функция, которая сопоставляет свои аргументы с образцами ''P<sub>1</sub>, …, P<sub>n</sub>'', и возвращает одно из выражений ''E<sub>1</sub>, …, E<sub>n</sub>''. (Если ни один образец не подошел, функция вместо этого выбросит исключение <tt>MatchError</tt>). Другими словами, выражение сверху это короткая запись анонимной функции
 
<code>
= Обобщенные типы и методы =
 
Классы в Scala могут иметь типовые параметры. Мы продемонстрируем использование типовых параметров на примере функциональных стеков. Скажем, нам нужно написать тип данных для стеков целых чисел с методами <tt>push</tt>, <tt>top</tt>, <tt>pop</tt> и <tt>isEmpty</tt>. Это можно сделать при помощи следующей иерархии классов:
 
<font size=3><syntaxhighlight lang=Scala>
</syntaxhighlight></font>
 
В данном определении '<tt>A</tt>' это ''типовой параметр'' класса <tt>Stack</tt> и его подклассов. Типовые параметры это произвольные имена; они заключены в квадратные, а не круглые скобки, чтобы их было просто отличить от параметров значений. Вот пример использования обобщенного класса:
 
<font size=3><syntaxhighlight lang=Scala>
</syntaxhighlight></font>
 
Параметры этого метода называются ''полиморфными''. Обобщенные методы также называются ''полиморфными''. Этот термин пришел из греческого языка, на котором он значит "«имеющий много форм"». Чтобы применить такой полиморфный метод, как <tt>isPrefix</tt>, надо передать ему типовые параметры так же, как и параметры значений. Например,
 
<font size=3><syntaxhighlight lang=Scala>
</syntaxhighlight></font>
 
Первый способ решить эту проблему  — ограничить допустимые типы, которые могут быть подставлены вместо типа <tt>A</tt>, теми, которые содержать методы <tt><</tt> и <tt>></tt> соответствующих типов. В стандартной библиотеке классов Scala есть трейт <tt>Ordered[A]</tt>, которые представляет значения, которые можно сравнивать (при помощи <tt><</tt> и <tt>></tt>) со значениями типа <tt>A</tt>. Этот трейт определен так:
 
<font size=3><syntaxhighlight lang=Scala>
</syntaxhighlight></font>
 
Обозначение параметра <tt>A <: Ordered[A]</tt> говорит, что <tt>A</tt> это типовой параметр, который должен быть подтипом <tt>Ordered[A]</tt>, т.е.то есть его значения должны быть сравнимы со значениями того же типа.
 
С этим ограничением мы можем реализовать остальные компоненты абстракции обобщенного множества, как мы делали в случае <tt>IntSet</tt> ранее:
Проблема, связанная с ограничениями типовых параметров, состоит в том, что их нужно обдумывать заранее: если бы мы не объявили, что <tt>Num</tt> это подкласс <tt>Ordered</tt>, мы бы не смогли использовать во множествах элементы типа <tt>Num</tt>. По той же причине типы, унаследованные из Java, такие, как <tt>Int</tt>, <tt>Double</tt> или <tt>String</tt> не являются подклассами <tt>Ordered</tt>, поэтому значения этих типов не могут быть использованы во множествах.
 
Более гибкий вариант, который допускает элементы этих типов, использует ''ограничения по видимости'' (view bounds) вместо простых ограничений по типам, которые мы видели раньше. Единственное изменение, которое нужно будет внести в наш пример,  — в типовых параметрах:
 
<font size=3><syntaxhighlight lang=Scala>
Пока все в порядке. Интуитивно, компилятор был прав, запретив процедуру <tt>update</tt> в ковариантном классе, потому что <tt>update</tt> может изменить состояние, и поэтому ставит под угрозу корректность ковариантного подтипирования.
 
Также существуют методы, которые не меняют состояние, но в которых типовой параметр тоже появляется контравариантно. Пример тому  — метод <tt>push</tt> в типе <tt>Stack</tt>. Опять же, компилятор Scala запретит определение этого метода для ковариантных стеков:
 
<font size=3><syntaxhighlight lang=Scala>
</syntaxhighlight></font>
 
Жаль, что так происходит, потому что, в отличие от массивов, стеки  — чисто функциональные структуры данных и поэтому должны позволять ковариантное подтипирование. Впрочем, есть способ решить эту проблему, используя полиморфные методы с нижними границами типовых параметров.
 
== Нижние границы ==
</syntaxhighlight></font>
 
Нижний граничный тип <tt>Nothing</tt> не содержит значения, так что тип <tt>Stack[Nothing]</tt> выражает факт того, что в <tt>EmptyStack</tt> нет элементов. Помимо этого, <tt>Nothing</tt> является подтипом всех других типов. Заметьте, что для ковариантных стеков <tt>Stack[Nothing]</tt>  — подтип <tt>Stack[T]</tt> для любого другого типа <tt>T</tt>. Поэтому можно использовать лишь единственный объект пустого стека в пользовательском коде. К примеру,
 
<font size=3><syntaxhighlight lang=Scala>
</syntaxhighlight></font>
 
Локальный вывод типов определит, что типовой параметр <tt>B</tt> должен быть <tt>String</tt> в применении <tt>EmptyStack.push("abc")</tt>. Результирующий тип этого применения  — <tt>Stack[String]</tt>, который, в свою очередь, имеет метод
<font size=3><syntaxhighlight lang=Scala>
push[B >: String](elem: B): Stack[B]
</syntaxhighlight></font>
 
Последняя часть определения значения, приведенного выше, это применение этого метода к <tt>'''new''' AnyRef()</tt>. Локальный вывод типов определит, что типовой параметр <tt>B</tt> должен на этот раз быть <tt>AnyRef</tt>, с результирующим типом <tt>Stack[AnyRef]</tt>. То есть, тип, присвоенный значению <tt>s</tt>  — <tt>Stack[AnyRef]</tt>.
 
Помимо <tt>Nothing</tt>, который является подтипом всех других типов, есть также тип <tt>Null</tt>, являющийся подтипом <tt>scala.AnyRef</tt> и всех классов, наследующих от него. Литерал <tt>'''null'''</tt> в Scala  — единственное значение этого типа, что делает этот литерал совместимым со всеми ссылочными типами, но не с типами значений, таких, как <tt>Int</tt>.
 
Мы завершим этот параграф полным улучшенным определением стеков. Теперь у них ковариантное подтипирование, метод <tt>push</tt> обобщен, и пустой стек представлен единственным объектом.
<font size=3><syntaxhighlight lang=Scala>
abstract class Stack[+A] {
</syntaxhighlight></font>
 
Многие классы в библиотеке Scala  — обобщенные. Теперь мы представим два часто используемых семейства обобщенных классов, кортежи и функции. Обсуждение других часто используемых классов, списков, приведено в следующей главе.
 
== Кортежи ==
Как обычно, типовые параметры конструкторов можно опустить, если они выводимы из аргументов. Есть также кортежные классы для любого другого количества элементов (нынешняя реализация Scala ограничивает кортежи по длине некоторым большим числом).
 
Как обращаться к элементам кортежей? Поскольку кортежи  — это case-классы, есть две возможности. Можно либо обращаться к полям кортежа, используя имена параметров конструктора ''_i'', как в этом примере:
 
<font size=3><syntaxhighlight lang=Scala>
</syntaxhighlight></font>
 
Заметьте, что типовые параметры никогда не используются в образцах, писать <tt>caseTuple2[Int, Int](n, d)</tt>  — нельзя.
 
Кортежи так удобны, что у Scala есть для них специальный синтаксис. Чтобы сформировать кортеж с ''n'' элементами ''x<sub>1</sub>, …, x<sub>n</sub>'', можно написать ''(x<sub>1</sub>, …, x<sub>n</sub>)''. Такая запись эквивалентна <tt>Tuple</tt>''n(x<sub>1</sub>, …, x<sub>n</sub>)''. Синтаксис (…) работает одинаково для кортежей и паттернов. С таким кортежным синтаксисом пример <tt>divmod</tt> можно записать так:
== Функции ==
 
Scala  — функциональный язык в том смысле, что функции  — значения первого класса. Scala также объектно-ориентированный язык в том смысле, что каждое значение является объектом. Из этого следует, что функции в Scala являются объектами. Например, функция из типа <tt>String</tt> в тип <tt>Int</tt> представлена экземпляром трейта <tt>Function1[String, Int]</tt>. Трейт <tt>Function1</tt> определен так:
 
<font size=3><syntaxhighlight lang=Scala>
</syntaxhighlight></font>
 
Помимо <tt>Function1</tt> есть также определения для функций любой другой арности (нынешняя реализация устанавливает некий разумный предел). То есть, для любого возможного числа параметров есть соответствующее определение. Синтаксис типа функции в Scala <tt>(T<sub>1</sub>, …, T<sub>n</sub>) => S</tt>  — это просто сокращение для параметризованого типа <tt>Function''n''[T<sub>1</sub>, …, T<sub>n</sub>, S]</tt>.
 
Scala использует одинаковый синтаксис ''f(x)'' для применения функции, вне зависимости от того, является ли ''f'' методом или функциональным объектом. Это возможно благодаря следующему соглашению: применение функции ''f(x)'', где ''f''  — объект (в противоположность методу) это сокращенная форма записи для ''f''.<tt>apply</tt>(''x''). Метод <tt>apply</tt>, принадлежащий типу функций, вставляется автоматически везде, где это необходимо.
 
Поэтому мы определяли операцию взятия элемента из массива в [[Scala в примерах#Аннотации вариантности|Параграфе 8.2]] при помощи метода <tt>apply</tt>. Для любого массива <tt>a</tt> операция взятия элемента <tt>a(i)</tt> это сокращенная форма записи <tt>a.apply(i)</tt>.
 
Функции  — это пример того, как полезны объявления контравариантных типовых параметров. Рассмотрим, например, следующий код:
 
<font size=3><syntaxhighlight lang=Scala>
</syntaxhighlight></font>
 
Присваивать значение <tt>g</tt> типа <tt>String => Int</tt> величине <tt>f</tt> типа <tt>AnyRef => Int</tt>  — корректно. Действительно, все, что можно сделать с функцией типа <tt>String => Int</tt>  — это передать ей строку, чтобы получить целое число. Очевидно, что то же самое верно для функции <tt>f</tt>: если мы передадим ей строку (или любой другой объект), мы получим целое число. Это показывает, что подтипирование функций контравариантно по типу аргумента, тогда как оно ковариантно по типу результата. Короче говоря, <math>S \Rightarrow T</math> это подтип <math>S' \Rightarrow T'</math>, если <math>S'</math>  — подтип <math>S</math> и <math>T</math>  — подтип <math>T'</math>.
 
'''Пример 8.6.1''' Рассмотрим код:
= Списки =
 
Списки  — важные структуры данных во многих программах на Scala. Список, состоящий из элементов ''x<sub>1</sub>, …, x<sub>n</sub>'', записывается так: <tt>List(x<sub>1</sub>, …, x<sub>n</sub>)</tt>. Вот примеры:
 
<font size=3><syntaxhighlight lang=Scala>
Списки похожи на массивы в таких языках, как C или Java, но есть три важных отличия. Во-первых, списки неизменяемы. То есть, элементы списка нельзя менять при помощи присваиваний. Во-вторых, у списков рекурсивная структура, тогда как массивы плоские. В третьих, списки поддерживают гораздо больше операций, чем обычные массивы.
 
== Использование списков ==
 
<font size=3>'''Тип List'''</font>
 
Как и массивы, списки ''гомогенны''. Это значит, все элементы списка  — одного типа. Тип списка с элементами типа <tt>T</tt> записывается как <tt>List[T]</tt> (похоже на <tt>T[]</tt> в Java).
 
<font size=3><syntaxhighlight lang=Scala>
<font size=3>'''Конструкторы списков'''</font>
 
Все списки строятся при помощи двух более фундаментальных конструкторов, <tt>Nil</tt> и <tt>::</tt> (произвносится "«cons"»). <tt>Nil</tt> выражает пустой список. Инфиксный оператор <tt>::</tt> выражает продление списка. То есть, <tt>x :: xs</tt> выражает список с первым элементом <tt>x</tt>, за которым идут элементы списка <tt>xs</tt>. Значения списков, приведенные выже, могут быть определены так (на самом деле, их предыдущие определения это синтаксический сахар для определений ниже):
 
<font size=3><syntaxhighlight lang=Scala>
 
Все операции со списками можно выразить при помощи следующих трех конструкций:
* <tt>head</tt>  — возвращает первый элемент списка;
* <tt>tail</tt>  — возвращает список, состоящий из всех элементов за исключением первого;
* <tt>isEmpty</tt>  — возвращает <tt>'''true'''</tt> тогда и только тогда, когда список пуст.
 
Эти операции определены как методы объектов-списков. Их можно вызвать, выбрав из списка, с которым мы работаем. Примеры:
Методы <tt>head</tt> и <tt>tail</tt> определены только для непустых списокв. Когда они выбраны из пустого списка, они выбрасывают исключение.
 
В качестве примера работы со списками рассмотрим сортировку элементов списка числе в возрастающем порядке. Простой способ сделать это  — ''сортировка вставками'', которая работает так: чтобы отсортировать непустой список с первым элементом <tt>x</tt> и остальными элементами <tt>xs</tt>, отсортируем оставшийся список <tt>xs</tt> и вставим элемент <tt>x</tt> на правильную позицию в результат. Сортировка пустого списка дает пустой список. Запишем это на Scala:
 
<font size=3><syntaxhighlight lang=Scala>
</syntaxhighlight></font>
 
<tt>List</tt>  — абстрактный класс, так что нельзя определять элементы, вызывая пустой конструктор <tt>List</tt> (например, при помощи new <tt>List</tt>). У класса есть типовой параметр <tt>A</tt>. Класс ковариантен по этому параметру, то есть, <tt>List[S] <: List[T]</tt> для всех типов <tt>S</tt> и <tt>T</tt>, таких что <tt>S <: T</tt>. Класс расположен в пакете scala. Этот пакет содержит наиболее важные стандартные классы Scala. <tt>List</tt> определяет несколько методов, объясненных ниже.
 
 
</syntaxhighlight></font>
 
<tt>xs.last</tt> возвращает последний элемент списка <tt>xs</tt>, а <tt>xs.init</tt>  — все элементы <tt>xs</tt>, кроме последнего. Обе эти функции проходят весь список, и поэтому менее эффективны, чем их аналоги <tt>head</tt> и <tt>tail</tt>. Вот реализация <tt>last</tt>:
 
<font size=3><syntaxhighlight lang=Scala>
</syntaxhighlight></font>
 
У метода <tt>apply</tt> в Scala специальное значение. Объект с этим методом может быть применен к аргументам, как если бы он был функцией. Например, чтобы выбрать третий элемент списка <tt>xs</tt>, можно написать или <tt>xs.apply(3)</tt>, или <tt>xs(3)</tt>  — второй вариант раскрывается в первый.
 
С <tt>take</tt> и <tt>drop</tt> мы можем создавать списки, состоящие их последовательных элементов данного списка. Чтобы создать список из элементов ''xs<sub>m</sub>, …, xs<sub>n-1</sub>'' списка <tt>xs</tt>, используйте
<font size=3>'''Продолжение списка'''</font>
 
Как и любой инфиксный оператор, <tt>::</tt> также реализован как метод объекта. В этом случае объект  — это удлиняемый список. Это возможно, потому что операторы, заканчивающиеся на символ ‘<tt>:</tt>’, обрабатываются в Scala специальным образом. Все такие операторы рассматриваются как методы своих правых операндов. Например, <tt>x :: y = y.::(x)</tt>, тогда как <tt>x + y = x.+(y)</tt>.
 
Заметьте, однако, что операнды бинарной операции в каждом случае вычисляются слева направо. Так что, если <tt>D</tt> и <tt>E</tt>  — выражение с возможными побочными эффектами, <tt>D :: E</tt> транслируется в <tt>{'''val''' x = D; E.::(x)}</tt>, чтобы сохранить порядок вычисления операндов слева направо.
 
Другое отличие между операторами, заканчивающимися на ‘<tt>:</tt>’, и другими операторами относится к их ассоциативности. Операторы, заканчивающиеся на ‘<tt>:</tt>’, правоассоциативны, тогда как остальные  — левоассоциативны. То есть, <tt>x :: y :: z = x :: (y :: z)</tt>, тогда как <tt>x + y + z = (x + y) + z</tt>.
 
Определение <tt>::</tt> как метода класса <tt>List</tt>:
</syntaxhighlight></font>
 
Заметьте, что <tt>::</tt> определен для всех элементов x типа B и списков типа <tt>List[A]</tt>, таких что тип <tt>B</tt>  — супертип типа <tt>A</tt>. Результатом в этом случае будет список элементов типа <tt>B</tt>. Это выражается типовым параметром <tt>B</tt> с нижней границей <tt>A</tt> в сигнатуре <tt>::</tt>.
 
 
<font size=3>'''Конкатенация списков'''</font>
 
Операция конкатенации похожа на <tt>::</tt> и записывается <tt>:::</tt>. Результат выполнения <tt>(xs ::: ys)</tt>  — список, состоящий их всех элементов <tt>xs</tt>, за которыми следуют все элементы <tt>ys</tt>. Поскольку оператор заканчивается на двоеточие, <tt>:::</tt> правоассоциативен и рассматривается как метод своего правого операнда. Следовательно,
 
<font size=3><syntaxhighlight lang=Scala>
</syntaxhighlight></font>
 
Эта реализация хороша тем, что она проста, но она не очень эффективна. Действительно, конкатенация выполняется для каждого элемента списка. Конкатенация списка занимает время, пропорциональное длине первого операнда. Следовательно, сложность <tt>reverse(xs)</tt>: ''n + (n - — 1) + … + 1 = n (n + 1) / 2'', где ''n''  — длина <tt>xs</tt>. Может ли реализовать reverse более эффективно? Позже мы увидим, что есть другая реализация, которая имеет линейную сложность.
 
== Пример: сортировка слиянием ==
 
Представленную ранее в этой главе сортировку вставками просто сформулировать, но она не очень эффективна. Ее средняя сложность пропорциональна квадрату длины входного списка. Теперь мы разработаем программу для сортировки элементов списка, которая более эффективна. Хороший алгоритм для этого  — сортировка слиянием, и работает он следующим образом.
 
Во-первых, если в списке ноль или один элемент, он уже отсортирован, поэтому возвращаем неизмененный список. Более длинные списки разделяются на два подсписка, каждый из которых содержит примерно половину элементов начального списка. Каждый подсписок сортируется рекурсивным вызовом сортирующей функции, и два получившихся отсортированных списка затем сливаются.
</syntaxhighlight></font>
 
Сложность <tt>msort</tt>  — ''O(N log(N))'', где ''N''  — длина входного списка. Чтобы понять, почему, заметим, что разделение списка пополам и слияние двух отсортированных списков занимает время, пропорциональное длине аргумента(ов). Каждый рекурсивный вызов msort разделяет количество элементов ввода пополам, поэтому происходит ''O(log(N))'' последовательных рекурсивных вызовов, пока не достигается базовый случай со списками длины <tt>1</tt>. Для более длинных списков каждый вызов ведет к двум дальнейшим вызовам. Суммировав, получаем, что на каждом из ''O(log(N))'' уровне вызова каждый элемент начального списка принимает участие в одной операции разделения и одной операции слияния. Сложность каждого уровня вызова пропорциональна ''O(N)''. Поскольку есть ''O(log(N))'' уровней, получим, что общая сложность пропорциональна ''O(N log(N))''. Эта сложность не зависит от начального распределения элементов в списке, поэтому сложность в худшем случае такая же, как и в среднем. Поэтому сортировка слиянием  — хороший алгоритм для сортировки списков.
 
Вот пример того, как используется <tt>msort</tt>:
</syntaxhighlight></font>
 
Операция, имеющая отношение к фильтрации  — проверка, удовлетворяют ли все элементы списка некому критерию. Можно также задаться дуальным вопросом, содержится ли в списке элемент, удовлетворяющий некому критерию. Эти операции воплощены в функциях высшего порядка <tt>forall</tt> и <tt>exists</tt> класса <tt>List</tt>.
 
<font size=3><syntaxhighlight lang=Scala>
</syntaxhighlight></font>
 
Чтобы проиллюстрировать, как используется <tt>forall</tt>, рассмотрим вопрос, является ли число простым. Число ''n''  — простое, если оно делится без остатка только на единицу и на самого себя. Самый прямолинейный способ  — проверять, равен ли остаток от деления ''n'' на все числа от <tt>2</tt> до ''n'' не включительно нулю. Список чисел может быть сгенерирован при помощи функции <tt>List.range</tt>, которая определена в объекте <tt>List</tt> следующим образом:
 
<font size=3><syntaxhighlight lang=Scala>
<font size=3>'''Свертки и редукции списков'''</font>
 
Еще одна частая операция  — объединение элементов списка при помощи какого-нибудь оператора. Например,
 
<code>
Какова будет разница в асимптотической сложности между двумя версиями <tt>flatten</tt>?
 
На самом деле, <tt>flatten</tt> предопределен вместе со множеством других полезных функций в объекте <tt>List</tt> стандартной библиотеки Scala. Его можно вызвать из пользовательской программы при помощи <tt>List.flatten</tt>. Обратить внимание, что <tt>flatten</tt> не является методом класса <tt>List</tt>  — это не имело бы смысла, поскольку он применяется только к спискам списков, а не к спискам вообще.
 
 
Мы можем использовать функции высшего порядка для работы со списками, чтобы выразить многие вычисления, которые обычно выражаются при помощи вложенных циклов в императивных языках.
 
Для примера рассмотрим следующую задачу: дано положительное целое число ''n'', найти все пары положительных чисел ''i'' и ''j'', где <tt>1 &le; j < i < n</tt>, таких что ''i + j''  — простое число. Например, если ''n = 7'', то пары таковы:
 
{| class="wikitable"
|}
 
Естественный путь решения этой задачи состоит из двух частей. На первом шаге сгенерируем последовательность всех пар целых чисел ''(i, j)'', таких что <tt>1 &le; j < i < n</tt>. На втором шаге отфильтруем из этой последовательности все пары ''(i, j)'', такие что ''i + j''  — простое число.
 
Посмотрим на первый шаг более детально. Естественный способ генерации последовательности пар состоит из трех подпунктов. Во-первых, сгенерируем все целые числа от <tt>1</tt> до ''n''. Во-вторых, для каждого целого числа ''i'' между <tt>1</tt> и ''n'' сгенерируем список пар от ''(i, 1)'' до ''(i, i - — 1)''. Это можно сделать при помощи комбинации <tt>range</tt> и <tt>map</tt>:
 
<font size=3><syntaxhighlight lang=Scala>
<font size=3>'''Сглаживающие преобразования'''</font>
 
Комбинация преобразования и затем конкатенации подсписков результатов преобразования  — настолько частая операция, что для этого есть специальный метод в классе <tt>List</tt>:
 
<font size=3><syntaxhighlight lang=Scala>
</syntaxhighlight></font>
 
При помощи <tt>flatMap</tt> выражение для пар, чья сумма  — простое число, можно записать более кратко:
 
<font size=3><syntaxhighlight lang=Scala>
 
= For-Comprehensions =
 
== Задача N ферзей ==
 
== Очереди с For-Comprehensions ==
 
== Трансляция For-Comprehensions ==
 
== Цикл For ==
 
== Обобщение For ==
 
= Изменяемое состояние =
 
== Объекты с состоянием ==
 
== Императивные структуры контроля ==
 
== Расширенный пример: симуляция распределенных событий ==
 
== Заключение ==
 
= Вычисления с потоками =
 
В предыдущих главах рассматривались переменные, присваивание и объекты, сохраняющие состояние. Мы видели, как объекты реального мира, которые изменяются со временем, могут быть смоделированы изменением состояния переменных в вычислении. Таким образом временные изменения в реальном мире моделируются временными изменениями в выполнении программы. Конечно, такие временные изменения обычно сокращены или растянуты, но их относительный порядок остается неизменным. Такой подход представляется вполне естественным, но за него приходится платить: наша простая и выразительная модель
подстановок для функционального вычисления будет более не применима, если мы введем переменные
и присваивание.
 
Есть ли другой способ? Можем ли мы моделировать изменение состояния в реальном мире, используя лишь функции без побочных эффектов? Руководствуясь математикой, определенно можно дать ответ: "«да"». Величина, изменяемая со временем, просто представляется функцией <tt>f(t)</tt> с параметром времени <tt>t</tt>. То же самое можно проделать с вычислениями, но вместо переписывания переменной последовательностью значений, мы представим все эти значения списком. Так что изменяемая переменная <tt>'''var''' x: T</tt> заменяется неизменяемым значением <tt>'''val''' x: List[T]</tt>. В сущности, мы поменяли память на время  — теперь различные значения переменной существуют одновременно, как различные элементы списка. Преимуществом такого подхода будет возможность "«путешествия по времени"», т.е.то есть просмотра нескольких последовательных значений одновременно. Другое преимущество заключается в том, что мы можем использовать мощную библиотеку функций над списками, и это часто упрощает вычисления. Например, рассмотрим императивный способ вычисления суммы всех простых чисел из некоторого
интервала:
 
</syntaxhighlight></font>
 
Заметьте, переменная <tt>i</tt> "«пробегает"» все значения из интервала <tt>[start .. end-1]</tt>.
 
Более функциональный способ заключается в представлении списка значений <tt>i</tt> явно, как <tt>range(start, end).</tt> Тогда функция может быть переписана так:
</syntaxhighlight></font>
 
Бесспорно, вторая программа короче и яснее! Однако функциональная программа также и менее эффективна, поскольку она конструирует список чисел из интервала, а затем еще один для простых чисел.
Еще хуже с точки зрения эффективности следующий пример.
 
(Эта функция, как и предыдущая, тоже определена в модуле <tt>Stream</tt>). Даже хотя <tt>Stream.range</tt> и <tt>List.range</tt> выглядят похоже, их поведение во время выполнения совершенно разное:
 
<tt>Stream.range</tt> немедленно возвращает объект <tt>Stream</tt>, первый элемент которого  — <tt>start</tt>. Все другие элементы вычисляются, только если они ''потребуются'' при помощи вызова метода <tt>tail</tt> (который может никогда не произойти).
 
Доступ к потокам  — такой же, как к спискам. Как и для списков, для потоков определены базовые методы доступа <tt>isEmpty</tt>, <tt>head</tt> и <tt>tail</tt>. Например, распечатать все элементы потока можно так:
 
<font size=3><syntaxhighlight lang=Scala>
Различие с предыдущей списковой реализацей в том, что теперь нет необходимости конструировать и проверять на простоту числа после <tt>1013</tt>.
 
'''Склеивание потоков.''' Два метода из класса <tt>List</tt>, не поддерживаемые классом <tt>Stream</tt> это <tt>::</tt> и <tt>:::</tt>. Причина в том, что эти методы раскрываются с правых аргументов, а это означает, что эти аргументы должны быть вычислены до вызова метода. Например, в случае <tt>x :: xs</tt> на списках, хвост <tt>xs</tt> должен быть вычислен до вызова оператора <tt>::</tt> и конструирования нового списка. Это не работает для потоков, поскольку хвост потока не должен вычисляться, пока не потребуется операции <tt>tail</tt>. Объяснение, почему метод <tt>:::</tt> не адаптируется для потоков  — аналогично.
 
Вместо <tt>x :: xs</tt> для создания потока с первым элементом <tt>x</tt> и (невычисленным) остатком <tt>xs</tt> используют <tt>Stream.cons(x, xs)</tt>. Вместо <tt>xs ::: ys</tt> используют операцию <tt>xs append ys</tt>.
 
= Итераторы =
 
== Методы итераторов ==
 
== Создание итераторов ==
 
== Использование итераторов ==
 
= Неявные(имплицитные) параметры и преобразования =
 
Неявные(имплицитные) параметры и преобразования — это мощные инструменты для настройки существующих библиотек и для создания высокоуровневых абстракций. Например, давайте начнем с абстрактного класса полугрупп, который поддерживает операцию сложения.
 
<font size=3><syntaxhighlight lang=Scala>
</syntaxhighlight></font>
 
А вот подкласс <tt>SemiGroup</tt>  — класс <tt>Monoid</tt>, который добавляет поле <tt>unit</tt> (единичный элемент):
 
<font size=3><syntaxhighlight lang=Scala>
</pre>
 
Если ключевое слово присутствует, то оно делает все параметры в списке неявными. Например, в следующей версии метода sum параметр m является неявным.
 
<font size=3><syntaxhighlight lang=Scala>
</syntaxhighlight></font>
 
Как можно заметить из примера, возможно комбинировать обычные и неявные параметры. Однако, для метода или конструктора может быть только один неявный параметр, и он должен быть последним.
 
Ключевое слово '''<tt>implicit</tt>''' может также быть использовано как модификатор в определениях и объявлениях. Примеры:
</syntaxhighlight></font>
 
Основная идея неявных параметров  — это то, что аргументы для них могут быть выведены из вызова метода. Если аргументы, отвечающие за секцию неявного параметра, отсутствуют, тогда они выводятся компилятором Scala.
 
Действительные аргументы, которые могут быть переданы в качестве неявного параметра,  — это все идентификаторы <tt>X</tt>, которые доступны в точке вызова метода без префикса и которые помечены как неявные.
 
Если существует несколько аргументов, подходящих по типу к неявному параметру, компилятор Scala выберет наиболее точный (специфичный), используя стандартные правила разрешения статической перегрузки. Допустим, вызывается
 
<font size=3><syntaxhighlight lang=Scala>
</syntaxhighlight></font>
 
в контексте, где доступны <tt>stringMonoid</tt> и <tt>intMonoid</tt>. Мы знаем, что формальный параметр метода <tt>sum</tt> должен быть типа <tt>Int</tt>. Единственное значение, подходящее к типу формального параметра <tt>Monoid[Int]</tt>, это <tt>intMonoid</tt>, поэтому этот объект и будет передан как неявный параметр.
 
Это обсуждение также показывает, что неявный параметр выводится после того, как выведен какой-нибудь типовой аргумент.
<font size=3>'''Неявные преобразования'''</font>
 
Пусть у вас есть выражение ''E'' типа ''T'', хотя ожидается тип ''S''. ''T'' не приводится к ''S'' ни одним из предопределенных преобразований. Тогда компилятор Scala попытается применить последнее средство: неявное преобразование ''I(E)''. Здесь, ''I''  — это идентификатор, выражающий неявное определение или параметр, доступный без префикса в точке преобразования, применимый к аргументам типа ''T'' и чей результирующий тип совместим с типом ''S''.
 
Неявные преобразования также могут быть применены в селекторах членов. Получив ''E.x'', где ''x''  — не член типа ''E'', компилятор Scala постарается добавить неявное преобразование ''I(E).x'' так, чтобы ''x'' был членом ''I(E)''.
 
Вот пример неявного преобразования функции, которая преобразует целые числа в экземпляры класса <tt>scala.Ordered</tt>:
<font size=3>'''View Bounds'''</font>
 
View bounds (ограничения по видимости)  — это удобный синтаксический сахар для неявных параметров. Рассмотрим обобщенный метод сортировки:
 
<font size=3><syntaxhighlight lang=Scala>
</syntaxhighlight></font>
 
Метод <tt>synchronized</tt> вычисляет свой аргумент <tt>e</tt> в режиме взаимного исключения  — в любое время только один поток может выполнять аргумент <tt>synchronized</tt> данного монитора.
 
Поток может приостановиться на мониторе, ожидая сигнала. Поток, вызвавший метод <tt>wait</tt>, ждет до вызова другим потоком метода <tt>notify</tt> на том же объекте. Вызовы <tt>notify</tt> при отсутствии потоков, ожидающих сигнала, игнорируются.
</syntaxhighlight></font>
 
В качестве примера использования мониторов  — реализация класса буфера с ограничением:
 
<font size=3><syntaxhighlight lang=Scala>
== Futures ==
 
''Future'' (будущее)  — это значение, которое вычисляется параллельно некоторому клиентскому потоку, чтобы быть использованным им немного позже. Future используется для облегчения параллельной обработки ресурсов. Типичное применение:
 
<font size=3><syntaxhighlight lang=Scala>
== Семафоры ==
 
Классический механизм синхронизации процессов  — ''семафор'' (semaphore, lock). Он предлагает два атомарных действия: ''занятие'' и ''освобождение''. Вот реализация простого семафора в Scala:
 
<font size=3><syntaxhighlight lang=Scala>
== Читатели/Писатели ==
 
Более сложная форма синхронизации различает ''читающие потоки'', которые имеют доступ к общему ресурсу, не модифицируя его, и потоки, которые могут и читать, и изменять ресурс - — ''писатели''. Для того, чтобы синхронизировать читателей и писателей, нам нужно реализовать действия ''startRead'', ''startWrite'', ''endRead'', ''endWrite'' так, что:
* одновременно может быть несколько читателей,
* в любой момент может только быть один писатель,
== Асинхронные каналы ==
 
Основной способ межпроцессной связи  — асинхронный канал. Его реализация использует следующий простой класс для связанных списков:
 
<font size=3><syntaxhighlight lang=Scala>
</syntaxhighlight></font>
 
Чтобы обеспечить вставку и удаление элементов в связанный список, каждая ссылка на список указывает на узел, который предшествует узлу—вершине списка. Пустые связанные списки начинаются с пустого узла, следующий узел которого  — <tt>'''null'''</tt>.
 
Класс канала использует связанный список, чтобы хранить данные, которые были посланы, но еще не были прочитаны. Потоки, которые хотят читать из пустого канала, регистрируются, инкрементируя поле <tt>nreaders</tt>, и ожидают извещения.
</syntaxhighlight></font>
 
Выражения, которые нужно выполнять (т.е.то есть аргументы <tt>future</tt>), пишутся в канал для заданий <tt>openJobs</tt>. ''Задание'' (Job) это объект с
* абстрактным типом <tt>T</tt>, который описывает результат вычисления задания,
* методом без параметров <tt>task</tt> типа <tt>T</tt>, который обозначает выражение, которое должно быть вычислено,
== Почтовые ящики ==
 
Почтовые ящики  — это высокоуровневые гибкие конструкции для синхронизации и взаимодействия процессов. Они позволяют посылать и получать сообщения. ''Сообщение'' в этом контексте  — произвольный объект. Есть специальное сообщение <tt>TIMEOUT</tt>, которое используется для сигнализиации о задержке:
 
<font size=3><syntaxhighlight lang=Scala>
</syntaxhighlight></font>
 
Единственные различия  — в ограниченном по времени вызове <tt>wait</tt> и выражении, следующим за этим.
 
== Акторы ==
 
В [[Scala в примерах#Программирование с акторами и сообщениями|Главе 3]] представлен набросок электронного аукциона. Этот сервис основывался на высокоуровневых процессах  — акторах, которые работают, проверяя сообщения в своих почтовых ящиках, используя сопоставление с образцом. Улучшенная и оптимизированная реализация акторов находится в пакете <tt>scala.actors</tt>. Здесь мы предоставим набросок упрощенной версии библиотеки акторов.
 
Код ниже отличается от реализации в пакете <tt>scala.actors</tt>, чтобы из примера было ясно, как можно реализовать простую версию акторов. Это не является описанием того, как акторы в действительности определены и реализованы в стандартной библиотеке Scala (это можно найти в документации Scala API).
</syntaxhighlight></font>
 
[[Категория:Языки программирования]]
[[Категория:Функциональное программирование]]
[[Категория:Объектно-ориентированное программирование]]
[[Категория:Scala]]
7086

правок