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

''Здесь ведется перевод книги Martin'аMartin’а Odersky [http://www.scala-lang.org/docu/files/ScalaByExample.pdf Scala by examples], которая описывает основные приемы программирования на языке [[w:Scala (язык программирования)|Scala<small>^↑</small>]]. Присоединяйтесь!''

'''Замечание.''' Мы в огромном долгу у чудесной книги Абельсона и Сассмана, "«Структура и интерпретация компьютерных программ"». Многие примеры и упражнения оттуда также приведены здесь. Конечно, рабочий язык в каждом случае был изменен с 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>Unit</tt> в Scala, грубо говоря, соответствует <tt>void</tt> в Java; он используется всякий раз, когда функция не возвращает какого-либо интересного значения. На самом деле, поскольку Scala это язык, ориентированный на выражения, каждая функция возвращает некоторый результат. Если нет явно заданного выражения, то предполагается значение по умолчанию, <tt>()</tt> (произносится "«unit"»). Это значение имеет тип <tt>Unit</tt>. Функции, возвращающие <tt>Unit</tt>, также называются ''процедурами''. Вот более "«ориентированная на выражения"» формулировка функции swap из первой реализации быстрой сортировки, которая выражает это явно:

Вот пример, который демонстрирует область применения, для которой Scala особенно хорошо подходит. Рассмотрим задачу по созданию электронного аукциона. Для реализации участников аукциона мы используем модель акторных процессов в [http://erlang.org Erlang]-стиле. Акторы  — это объекты, которым посылаются сообщения. У каждого актора есть "«почтовый ящик"» для поступающих сообщений, который представлен очередью. Сообщения в очереди могут обрабатываться или в последовательном порядке, или выборочно, как удовлетворяющие некоторому образцу.

* Последняя вариация в <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>.

Преимущество подобного библиотечного подхода к многопоточности ''(см. также [http://lamp.epfl.ch/~cremet/publications/pilib.pdf PiLib]) ''  — в относительной простоте основного языка и гибкости для разработчиков библиотек. Поскольку основному языку не нужно определять детали высокоуровневого обмена информацией между процессами, он может оставаться простым и более общим. Поскольку конкретная модель сообщений в почтовом ящике  — библиотечный модуль, она может свободно быть модифицирована, если это требуется в каких-то приложениях. Впрочем, для такого подхода необходимо, чтобы базовый язык был достаточно выразителен, чтобы он мог обеспечивать необходимые языковые абстракции удобным способом. Scala разработан с учетом этого требования; одна из основных целей при проектировании заключалась в том, чтобы сделать его достаточно гибким, чтобы он мог выступать удобной платформой для доменно-специфичных языков, реализованных как библиотечные модули. Например, представленные выше конструкции для коммуникации между акторами могут рассматриваться как доменно-специфичный язык, который, в принципе, расширяет ядро Scala.

В дистрибутив Scala входит интерпретатор, который можно рассматривать как сложный калькулятор. Пользователь взаимодействует с калькулятором, вводя выражения. Калькулятор возвращает результаты вычислений и их типы. Например,

Имя, определенное при помощи <tt>'''def'''</tt>, вычисляется путем замены имени на (невычисленную) правую часть определения. Имя, определенное при помощи <tt>'''val'''</tt>, вычисляется путем замены имени на значение правой части. Процесс вычисления заканчивается, когда приходит к одному значению. Значение  — это некоторые данные, как например: строка, число, массив или список.

Параметры функций перечисляются после имени функции и всегда заключаются в скобки. Каждый параметр имеет тип, который указывается после имени параметра и двоеточия. Пока что нам потребуются только базовые числовые типы, такие как <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>.

Теперь проиллюстрируем элементы языка, которые мы упомянули к этому моменту, более интересной программой. Задание  — написать функцию

Обычный способ вычисления квадратных корней  — ньютоновский метод последовательных приближений. Мы начинаем с первой догадки <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>.

Несмотря на то, что на самом деле Scala не переписывает термы, затраты по памяти будут такими же, что и в последовательности вывода. Заметим, что в реализации <tt>gcd</tt> рекурсивный вызов <tt>gcd</tt>  — это последнее действие в теле вычисления. Это пример хвостовой рекурсии. Последний вызов в хвостово-рекурсивной функции может быть реализован прыжком обратно к началу этой функции. Аргументы такого вызова могут быть вписаны на место параметров текущего выполнения <tt>gcd</tt>, так что новой памяти на стеке выделять не нужно. Отметим, что хвостово-рекурсивные функции это итеративные процессы, которые могут выполняться в константной памяти.

= Функции первого класса =

Функции в Scala являются "«значениями первого класса"». Как любые другие значения, их можно передавать как параметры и возвращать как результаты. Функции, которые принимают другие функции в качестве параметров или возвращают их как результаты, называются ''функциями высшего порядка''. Эта глава представляет функции высшего порядка и показывает гибкий механизм для составления программ, которые они реализуют.

3. Написать функцию для суммирования степеней двойки ''2ⁿ'' для всех целых чисел между двумя данными числами <tt>a</tt> и <tt>b</tt>:

Тип <tt>Int => Int</tt>  — это тип функции, которая принимает аргумент типа <tt>Int</tt> и возвращает результат типа <tt>Int</tt>. Так что <tt>sum</tt>  — функция, берущая в качестве параметра другую функцию. Другими словами, <tt>sum</tt>  — функция высшего порядка.

Часть перед стрелкой  — параметры функции, часть после нее  — тело функции. Вот, например, анонимная функция, перемножающая два аргумента:

Выражение Scala <tt>(x₁: T₁, …, x_n: T_n) => E</tt> определяет функцию, которая соотносит свои параметры <tt>x₁, …, x_n</tt> с результатами выражения <tt>E</tt> (где <tt>E</tt> может ссылаться на <tt>x₁, …, x_n</tt>). Анонимные функции  — не основные элементы языка Scala, поскольку они всегда могут быть выражены через именованные функции. Действительно, анонимная функция

где <tt>f</tt>  — свежее имя, которое больше не используется нигде в программе. Можно сказать, что анонимные функции это "«синтаксический сахар"».

В этой формулировке <tt>sum</tt>  — это функция, которая возвращает другую функцию, а именно специализированную суммирующую функцию <tt>sumF</tt>. Эта последняя функция выполняет всю работу: она принимает границы <tt>a</tt> и <tt>b</tt> как параметры, применяет <tt>f</tt>, параметр <tt>sum</tt>, ко всем целым числам между ними, и суммирует результаты.

Такая запись возможна, потому что применение функций левоассоциативно. То есть, если args₁ и args₂  — списки аргументов, то ''f''(args₁)(args₂) эквивалентно (''f''(args₁))(args₂).

где <tt>g</tt>  — свежий идентификатор. Или, если короче, с использованием анонимной фунции:

Тип функции, возвращающей функцию, выражается аналогично списку ее параметров. Возьмем к примеру последнюю формулировку <tt>sum</tt>. Тип <tt>sum</tt>  — <tt>(Int => Int) => (Int, Int) => Int</tt>. Это возможно, потому что типы функций правоассоциативны. То есть, <tt>T1 => T2 => T3</tt> эквивалентно <tt>T1 => (T2 => T3)</tt>.

Заметьте, что <tt>sqrt(x)</tt>  — неподвижная точка функции <tt>y => x / y</tt>. Поэтому <tt>sqrt(x)</tt> можно вычислить при помощи итерации неподвижной точки:

В предыдущей главе мы видели, что функции  — это очень важные абстракции, потому что они позволяют нам вводить общие методы вычислений как явные, именованные элементы нашего языка программирования. Настоящая глава показала, что эти абстракции могут быть скомбинированы при помощи функций высшего порядка, для создания дальнейших абстракций. Как программисты, мы должны искать возможности абстрагировать и переиспользовать. Самый высокий возможный уровень асбтракции не всегда самый лучший, но важно знать техники абстракции, чтобы уметь использовать их, где это уместно.

Программы Scala  — это последовательности символов Unicode. Мы различаем следующие множества символов:

</pre>

Литералы  — те же, что и в Java. Они определяют числа, символы, строки и булевские величины. Примеры литералов: <tt>0</tt>, <tt>1.0e10</tt>, <tt>'x'</tt>, <tt>"he said "hi!""</tt> или <tt>'''true'''</tt>.

Это определяет <tt>Rational</tt> как класс, принимающий два аргумента конструктора <tt>n</tt> и <tt>d</tt>, содержащие числитель и знаменатель числа. Класс предоставляет поля, возвращающие эти части, и методы для арифметических операций с рациональными числами. Левый операнд операции  — всегда рациональное число, для которого метод является членом (класса).

У каждого класса в Scala есть предок в иерархии (суперкласс), который расширяется данным классом. Если класс не упоминает предка в своем определении, предком неявно предполагается корневой тип <tt>scala.AnyRef</tt> (для реализаций Java этот тип  — псевдоним <tt>java.lang.Object</tt>). Например, класс <tt>Rational</tt> можно эквивалентно определить так:

В отличие от Java, методы в Scala не обязательно должны принимать список параметров. Пример тому  — метод <tt>square</tt>, представленный ниже. Этот метод вызывается просто упоминанием своего имени.

И <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>.

Проблема этого подхода в том, что такое определение значения нелегально для высшего уровня в Scala, оно должно быть частью другогодрtt>xугого класса или объекта. К тому же определение класса <tt>EmptySet</tt> теперь выглядит несколько избыточным  — зачем определять класс объектов, если нам нужен только один объект этого класса? Более прямой подход  — использовать ''определение объекта''. Ниже представлен более прямолинейный вариант определения пустого множества:

Scala  — чисто объектно-ориентированный язык. Это значит, что каждое значение в Scala может быть рассмотрено как объект. На самом деле даже примитивные типы, как <tt>int</tt> или <tt>boolean</tt>, не рассматриваются специально. Они определены как псевдонимы типов классов Scala в модуле <tt>Predef</tt>:

Для эффективности компилятор обычно представляет значения типа <tt>scala.Int</tt> 32-битными целыми числами, значения <tt>scala.Boolean</tt>  — двоичными значениями Java, и  т. д. Но он преобразует эти специализированные представления в объекты, когда это требуется, например, когда значение примитивного типа <tt>Int</tt> передается в функцию с параметром типа <tt>AnyRef</tt>. Обратите внимание, что специальное представление примитивных значений это всего лишь оптимизация, оно не меняет смысла программы.

Класс <tt>Int</tt> можно в принципе реализовать, используя только объекты и классы, без ссылок на встроенный тип целых чисел. Чтобы понять, как это сделать, рассмотрим более простую задачу реализации типа <tt>Nat</tt> натуральных (т.е.то есть неотрицательных) чисел. Вот определение абстрактного класса <tt>Nat</tt>:

Объектно-ориентированное программирование обещает, что такие модификации не обязательны, поскольку их можно избежать, переиспользуя существующий неизменяющийся код через механизм наследования. Действительно, более объектно-ориентированная организация решает проблему. Идея состоит в том, чтобы сделать операцию "«высшего уровня"» <tt>eval</tt> методом каждого класса выражений вместо того, чтобы реализовывать ее как функцию вне иерархии классов выражений, как мы делали прежде. Поскольку <tt>eval</tt> теперь  — метод всех классов выражений, классификация и методы доступа становятся излишними, и реализация сильно упрощается:

Из этого примера мы можем сделать вывод, что объектно-ориентированная организация  — это лучшим подход для создания систем, которые должны быть расширяемы новыми типами данных. Но есть и другой способ, которым мы можем захотеть расширить пример с выражениями. Мы можем также захотеть добавить новые ''операции'' с выражениями. Например, добавить операцию, которая выводит на экран вывода дерево выражения.

''Case-классы'' и ''case-объекты'' (вариации) определяются как обычные классы и объекты, за исключением того, что перед определением ставится модифиатор <tt>'''case'''</tt>. Например, определения

2. У case-классов и case-объектов есть неявные реализации методов <tt>toString</tt>, <tt>equals</tt> и <tt>hashCode</tt>, которые переписывают одноименные методы класса <tt>AnyRef</tt>. Реализация этих методов принимает во внимание структуру членов case-класса в каждом случае. Метод <tt>toString</tt> представляет дерево выражения так, как оно было сконструировано. Поэтому

который возвращает параметр конструктора <tt>n</tt>, а у <tt>Sum</tt>  — два метода

Заметьте, что для значения <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>? Это решается четвертым и последним пунктом.

В этом примере есть два случая. Каждый случай сопоставляет образец с выражением. Образцы сопоставляются со значениями селектора <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₁, v₂)</tt> и связывает переменные образца <tt>l</tt> и <tt>r</tt> с <tt>v₁</tt> и <tt>v₂</tt> соответственно.

До этого case-выражения всегда появлялись вместе с оператором <tt>match</tt>. Но можно также использовать case-выражения сами по себе. Блок case-выражений, такой как

это функция, которая сопоставляет свои аргументы с образцами ''P₁, …, P_n'', и возвращает одно из выражений ''E₁, …, E_n''. (Если ни один образец не подошел, функция вместо этого выбросит исключение <tt>MatchError</tt>). Другими словами, выражение сверху это короткая запись анонимной функции

Классы в Scala могут иметь типовые параметры. Мы продемонстрируем использование типовых параметров на примере функциональных стеков. Скажем, нам нужно написать тип данных для стеков целых чисел с методами <tt>push</tt>, <tt>top</tt>, <tt>pop</tt> и <tt>isEmpty</tt>. Это можно сделать при помощи следующей иерархии классов:

В данном определении '<tt>A</tt>' это ''типовой параметр'' класса <tt>Stack</tt> и его подклассов. Типовые параметры это произвольные имена; они заключены в квадратные, а не круглые скобки, чтобы их было просто отличить от параметров значений. Вот пример использования обобщенного класса:

Параметры этого метода называются ''полиморфными''. Обобщенные методы также называются ''полиморфными''. Этот термин пришел из греческого языка, на котором он значит "«имеющий много форм"». Чтобы применить такой полиморфный метод, как <tt>isPrefix</tt>, надо передать ему типовые параметры так же, как и параметры значений. Например,

Первый способ решить эту проблему  — ограничить допустимые типы, которые могут быть подставлены вместо типа <tt>A</tt>, теми, которые содержать методы <tt><</tt> и <tt>></tt> соответствующих типов. В стандартной библиотеке классов Scala есть трейт <tt>Ordered[A]</tt>, которые представляет значения, которые можно сравнивать (при помощи <tt><</tt> и <tt>></tt>) со значениями типа <tt>A</tt>. Этот трейт определен так:

Обозначение параметра <tt>A <: Ordered[A]</tt> говорит, что <tt>A</tt> это типовой параметр, который должен быть подтипом <tt>Ordered[A]</tt>, т.е.то есть его значения должны быть сравнимы со значениями того же типа.

Более гибкий вариант, который допускает элементы этих типов, использует ''ограничения по видимости'' (view bounds) вместо простых ограничений по типам, которые мы видели раньше. Единственное изменение, которое нужно будет внести в наш пример,  — в типовых параметрах:

Также существуют методы, которые не меняют состояние, но в которых типовой параметр тоже появляется контравариантно. Пример тому  — метод <tt>push</tt> в типе <tt>Stack</tt>. Опять же, компилятор Scala запретит определение этого метода для ковариантных стеков:

Жаль, что так происходит, потому что, в отличие от массивов, стеки  — чисто функциональные структуры данных и поэтому должны позволять ковариантное подтипирование. Впрочем, есть способ решить эту проблему, используя полиморфные методы с нижними границами типовых параметров.

Нижний граничный тип <tt>Nothing</tt> не содержит значения, так что тип <tt>Stack[Nothing]</tt> выражает факт того, что в <tt>EmptyStack</tt> нет элементов. Помимо этого, <tt>Nothing</tt> является подтипом всех других типов. Заметьте, что для ковариантных стеков <tt>Stack[Nothing]</tt>  — подтип <tt>Stack[T]</tt> для любого другого типа <tt>T</tt>. Поэтому можно использовать лишь единственный объект пустого стека в пользовательском коде. К примеру,

Локальный вывод типов определит, что типовой параметр <tt>B</tt> должен быть <tt>String</tt> в применении <tt>EmptyStack.push("abc")</tt>. Результирующий тип этого применения  — <tt>Stack[String]</tt>, который, в свою очередь, имеет метод

Последняя часть определения значения, приведенного выше, это применение этого метода к <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>.

Многие классы в библиотеке Scala  — обобщенные. Теперь мы представим два часто используемых семейства обобщенных классов, кортежи и функции. Обсуждение других часто используемых классов, списков, приведено в следующей главе.

Как обращаться к элементам кортежей? Поскольку кортежи  — это case-классы, есть две возможности. Можно либо обращаться к полям кортежа, используя имена параметров конструктора ''_i'', как в этом примере:

Заметьте, что типовые параметры никогда не используются в образцах, писать <tt>caseTuple2[Int, Int](n, d)</tt>  — нельзя.

Scala  — функциональный язык в том смысле, что функции  — значения первого класса. Scala также объектно-ориентированный язык в том смысле, что каждое значение является объектом. Из этого следует, что функции в Scala являются объектами. Например, функция из типа <tt>String</tt> в тип <tt>Int</tt> представлена экземпляром трейта <tt>Function1[String, Int]</tt>. Трейт <tt>Function1</tt> определен так:

Помимо <tt>Function1</tt> есть также определения для функций любой другой арности (нынешняя реализация устанавливает некий разумный предел). То есть, для любого возможного числа параметров есть соответствующее определение. Синтаксис типа функции в Scala <tt>(T₁, …, T_n) => S</tt>  — это просто сокращение для параметризованого типа <tt>Function''n''[T₁, …, T_n, S]</tt>.

Scala использует одинаковый синтаксис ''f(x)'' для применения функции, вне зависимости от того, является ли ''f'' методом или функциональным объектом. Это возможно благодаря следующему соглашению: применение функции ''f(x)'', где ''f''  — объект (в противоположность методу) это сокращенная форма записи для ''f''.<tt>apply</tt>(''x''). Метод <tt>apply</tt>, принадлежащий типу функций, вставляется автоматически везде, где это необходимо.

Функции  — это пример того, как полезны объявления контравариантных типовых параметров. Рассмотрим, например, следующий код:

Присваивать значение <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>.

Списки  — важные структуры данных во многих программах на Scala. Список, состоящий из элементов ''x₁, …, x_n'', записывается так: <tt>List(x₁, …, x_n)</tt>. Вот примеры:

Как и массивы, списки ''гомогенны''. Это значит, все элементы списка  — одного типа. Тип списка с элементами типа <tt>T</tt> записывается как <tt>List[T]</tt> (похоже на <tt>T[]</tt> в Java).

Все списки строятся при помощи двух более фундаментальных конструкторов, <tt>Nil</tt> и <tt>::</tt> (произвносится "«cons"»). <tt>Nil</tt> выражает пустой список. Инфиксный оператор <tt>::</tt> выражает продление списка. То есть, <tt>x :: xs</tt> выражает список с первым элементом <tt>x</tt>, за которым идут элементы списка <tt>xs</tt>. Значения списков, приведенные выже, могут быть определены так (на самом деле, их предыдущие определения это синтаксический сахар для определений ниже):

* <tt>head</tt>  — возвращает первый элемент списка;

* <tt>tail</tt>  — возвращает список, состоящий из всех элементов за исключением первого;

* <tt>isEmpty</tt>  — возвращает <tt>'''true'''</tt> тогда и только тогда, когда список пуст.

В качестве примера работы со списками рассмотрим сортировку элементов списка числе в возрастающем порядке. Простой способ сделать это  — ''сортировка вставками'', которая работает так: чтобы отсортировать непустой список с первым элементом <tt>x</tt> и остальными элементами <tt>xs</tt>, отсортируем оставшийся список <tt>xs</tt> и вставим элемент <tt>x</tt> на правильную позицию в результат. Сортировка пустого списка дает пустой список. Запишем это на Scala:

<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> определяет несколько методов, объясненных ниже.

<tt>xs.last</tt> возвращает последний элемент списка <tt>xs</tt>, а <tt>xs.init</tt>  — все элементы <tt>xs</tt>, кроме последнего. Обе эти функции проходят весь список, и поэтому менее эффективны, чем их аналоги <tt>head</tt> и <tt>tail</tt>. Вот реализация <tt>last</tt>:

У метода <tt>apply</tt> в Scala специальное значение. Объект с этим методом может быть применен к аргументам, как если бы он был функцией. Например, чтобы выбрать третий элемент списка <tt>xs</tt>, можно написать или <tt>xs.apply(3)</tt>, или <tt>xs(3)</tt>  — второй вариант раскрывается в первый.

Как и любой инфиксный оператор, <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> определен для всех элементов x типа B и списков типа <tt>List[A]</tt>, таких что тип <tt>B</tt>  — супертип типа <tt>A</tt>. Результатом в этом случае будет список элементов типа <tt>B</tt>. Это выражается типовым параметром <tt>B</tt> с нижней границей <tt>A</tt> в сигнатуре <tt>::</tt>.

Операция конкатенации похожа на <tt>::</tt> и записывается <tt>:::</tt>. Результат выполнения <tt>(xs ::: ys)</tt>  — список, состоящий их всех элементов <tt>xs</tt>, за которыми следуют все элементы <tt>ys</tt>. Поскольку оператор заканчивается на двоеточие, <tt>:::</tt> правоассоциативен и рассматривается как метод своего правого операнда. Следовательно,

Эта реализация хороша тем, что она проста, но она не очень эффективна. Действительно, конкатенация выполняется для каждого элемента списка. Конкатенация списка занимает время, пропорциональное длине первого операнда. Следовательно, сложность <tt>reverse(xs)</tt>: ''n + (n - — 1) + … + 1 = n (n + 1) / 2'', где ''n''  — длина <tt>xs</tt>. Может ли реализовать reverse более эффективно? Позже мы увидим, что есть другая реализация, которая имеет линейную сложность.

Представленную ранее в этой главе сортировку вставками просто сформулировать, но она не очень эффективна. Ее средняя сложность пропорциональна квадрату длины входного списка. Теперь мы разработаем программу для сортировки элементов списка, которая более эффективна. Хороший алгоритм для этого  — сортировка слиянием, и работает он следующим образом.

Сложность <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>forall</tt> и <tt>exists</tt> класса <tt>List</tt>.

Чтобы проиллюстрировать, как используется <tt>forall</tt>, рассмотрим вопрос, является ли число простым. Число ''n''  — простое, если оно делится без остатка только на единицу и на самого себя. Самый прямолинейный способ  — проверять, равен ли остаток от деления ''n'' на все числа от <tt>2</tt> до ''n'' не включительно нулю. Список чисел может быть сгенерирован при помощи функции <tt>List.range</tt>, которая определена в объекте <tt>List</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'', то пары таковы:

Естественный путь решения этой задачи состоит из двух частей. На первом шаге сгенерируем последовательность всех пар целых чисел ''(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>:

Комбинация преобразования и затем конкатенации подсписков результатов преобразования  — настолько частая операция, что для этого есть специальный метод в классе <tt>List</tt>:

При помощи <tt>flatMap</tt> выражение для пар, чья сумма  — простое число, можно записать более кратко:

В предыдущих главах рассматривались переменные, присваивание и объекты, сохраняющие состояние. Мы видели, как объекты реального мира, которые изменяются со временем, могут быть смоделированы изменением состояния переменных в вычислении. Таким образом временные изменения в реальном мире моделируются временными изменениями в выполнении программы. Конечно, такие временные изменения обычно сокращены или растянуты, но их относительный порядок остается неизменным. Такой подход представляется вполне естественным, но за него приходится платить: наша простая и выразительная модель

Есть ли другой способ? Можем ли мы моделировать изменение состояния в реальном мире, используя лишь функции без побочных эффектов? Руководствуясь математикой, определенно можно дать ответ: "«да"». Величина, изменяемая со временем, просто представляется функцией <tt>f(t)</tt> с параметром времени <tt>t</tt>. То же самое можно проделать с вычислениями, но вместо переписывания переменной последовательностью значений, мы представим все эти значения списком. Так что изменяемая переменная <tt>'''var''' x: T</tt> заменяется неизменяемым значением <tt>'''val''' x: List[T]</tt>. В сущности, мы поменяли память на время  — теперь различные значения переменной существуют одновременно, как различные элементы списка. Преимуществом такого подхода будет возможность "«путешествия по времени"», т.е.то есть просмотра нескольких последовательных значений одновременно. Другое преимущество заключается в том, что мы можем использовать мощную библиотеку функций над списками, и это часто упрощает вычисления. Например, рассмотрим императивный способ вычисления суммы всех простых чисел из некоторого

Заметьте, переменная <tt>i</tt> "«пробегает"» все значения из интервала <tt>[start .. end-1]</tt>.

Бесспорно, вторая программа короче и яснее! Однако функциональная программа также и менее эффективна, поскольку она конструирует список чисел из интервала, а затем еще один для простых чисел.

<tt>Stream.range</tt> немедленно возвращает объект <tt>Stream</tt>, первый элемент которого  — <tt>start</tt>. Все другие элементы вычисляются, только если они ''потребуются'' при помощи вызова метода <tt>tail</tt> (который может никогда не произойти).

Доступ к потокам  — такой же, как к спискам. Как и для списков, для потоков определены базовые методы доступа <tt>isEmpty</tt>, <tt>head</tt> и <tt>tail</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>SemiGroup</tt>  — класс <tt>Monoid</tt>, который добавляет поле <tt>unit</tt> (единичный элемент):

Если ключевое слово присутствует, то оно делает все параметры в списке неявными. Например, в следующей версии метода sum параметр m является неявным.

Как можно заметить из примера, возможно комбинировать обычные и неявные параметры. Однако, для метода или конструктора может быть только один неявный параметр, и он должен быть последним.

Основная идея неявных параметров  — это то, что аргументы для них могут быть выведены из вызова метода. Если аргументы, отвечающие за секцию неявного параметра, отсутствуют, тогда они выводятся компилятором Scala.

Действительные аргументы, которые могут быть переданы в качестве неявного параметра,  — это все идентификаторы <tt>X</tt>, которые доступны в точке вызова метода без префикса и которые помечены как неявные.

Если существует несколько аргументов, подходящих по типу к неявному параметру, компилятор Scala выберет наиболее точный (специфичный), используя стандартные правила разрешения статической перегрузки. Допустим, вызывается

в контексте, где доступны <tt>stringMonoid</tt> и <tt>intMonoid</tt>. Мы знаем, что формальный параметр метода <tt>sum</tt> должен быть типа <tt>Int</tt>. Единственное значение, подходящее к типу формального параметра <tt>Monoid[Int]</tt>, это <tt>intMonoid</tt>, поэтому этот объект и будет передан как неявный параметр.

Пусть у вас есть выражение ''E'' типа ''T'', хотя ожидается тип ''S''. ''T'' не приводится к ''S'' ни одним из предопределенных преобразований. Тогда компилятор Scala попытается применить последнее средство: неявное преобразование ''I(E)''. Здесь, ''I''  — это идентификатор, выражающий неявное определение или параметр, доступный без префикса в точке преобразования, применимый к аргументам типа ''T'' и чей результирующий тип совместим с типом ''S''.

Неявные преобразования также могут быть применены в селекторах членов. Получив ''E.x'', где ''x''  — не член типа ''E'', компилятор Scala постарается добавить неявное преобразование ''I(E).x'' так, чтобы ''x'' был членом ''I(E)''.

View bounds (ограничения по видимости)  — это удобный синтаксический сахар для неявных параметров. Рассмотрим обобщенный метод сортировки:

Метод <tt>synchronized</tt> вычисляет свой аргумент <tt>e</tt> в режиме взаимного исключения  — в любое время только один поток может выполнять аргумент <tt>synchronized</tt> данного монитора.

В качестве примера использования мониторов  — реализация класса буфера с ограничением:

''Future'' (будущее)  — это значение, которое вычисляется параллельно некоторому клиентскому потоку, чтобы быть использованным им немного позже. Future используется для облегчения параллельной обработки ресурсов. Типичное применение:

Классический механизм синхронизации процессов  — ''семафор'' (semaphore, lock). Он предлагает два атомарных действия: ''занятие'' и ''освобождение''. Вот реализация простого семафора в Scala:

Более сложная форма синхронизации различает ''читающие потоки'', которые имеют доступ к общему ресурсу, не модифицируя его, и потоки, которые могут и читать, и изменять ресурс - — ''писатели''. Для того, чтобы синхронизировать читателей и писателей, нам нужно реализовать действия ''startRead'', ''startWrite'', ''endRead'', ''endWrite'' так, что:

Основной способ межпроцессной связи  — асинхронный канал. Его реализация использует следующий простой класс для связанных списков:

Чтобы обеспечить вставку и удаление элементов в связанный список, каждая ссылка на список указывает на узел, который предшествует узлу—вершине списка. Пустые связанные списки начинаются с пустого узла, следующий узел которого  — <tt>'''null'''</tt>.

Выражения, которые нужно выполнять (т.е.то есть аргументы <tt>future</tt>), пишутся в канал для заданий <tt>openJobs</tt>. ''Задание'' (Job) это объект с

Почтовые ящики  — это высокоуровневые гибкие конструкции для синхронизации и взаимодействия процессов. Они позволяют посылать и получать сообщения. ''Сообщение'' в этом контексте  — произвольный объект. Есть специальное сообщение <tt>TIMEOUT</tt>, которое используется для сигнализиации о задержке:

Единственные различия  — в ограниченном по времени вызове <tt>wait</tt> и выражении, следующим за этим.

В [[Scala в примерах#Программирование с акторами и сообщениями|Главе 3]] представлен набросок электронного аукциона. Этот сервис основывался на высокоуровневых процессах  — акторах, которые работают, проверяя сообщения в своих почтовых ящиках, используя сопоставление с образцом. Улучшенная и оптимизированная реализация акторов находится в пакете <tt>scala.actors</tt>. Здесь мы предоставим набросок упрощенной версии библиотеки акторов.