Мартин Одерский
Введение в функциональное программирование на скале
Конспект лекций. Версия 0.1
[Это конспект лекций «Functional Programming Principles in Scala» (второй сезон, сентябрь—ноябрь 2013 г.). Конспект близко следует тексту лекций, а текст — слайдам, поэтому он близок к переводу слайдов. Очевидные оговорки и несоответствия исправлены (если это более чем исправленный вид кавычки, исправление оговорено в квадратных скобках), код приведен к интерпретируемому виду. Нумерация и названия параграфов тоже мои, они далеко не всегда совпадают с названиями лекций или заголовками слайдов.
Максим Отставнов, декабрь 2013 г.]
Оглавление
§ 1. Парадигмы программирования
§ 2. Элементы программирования на скале
§ 3. Стратегии и завершимость вычислений
§ 4. Условные выражения и определение значений
§ 5. Квадратный корень методом Ньютона
§ 6. Блоки и область лексической видимости
§ 10. Пример: поиск неподвижных точек
§ 12. Определение классов и создание объектов
§ 16. Методы и инфиксные операции
§ 17. Иерархии классов и объекты-одиночки
§ 25. Подтипизация и обобщения. Ковариантность
§ 28. Функциональная декомпозиция (разбор по шаблону)
§ 29. Списки и операции над ними
§ 30. Ускорение сортировки списков
§ 33. Высокопорядковые функции над списками
§ 34. Как рассуждать о списках
§ 35. Другие регулярные типы («коллекции»)
§ 36. Комбинаторный поиск и for-выражения
§ 39. Во что раскрываются «for»
§ 42. Сортировка и группировка регулярных структур
§ 44. Структурная индукция на деревьях
§ 47. Работа с бесконечными последовательностями
§ 48. Задача о переливании воды
Основными парадигмами программирования являются императивная, функциональная и логическая. Объектная ориентация ортогональна делению на парадигмы.
Императивное программирование связано с изменением значений изменяемых переменных, использованием присваиваний и управляющих структур, таких как условное исполнение, циклы, выходы и продолжения, возвраты из процедур. Эти понятия соответствуют ячейкам памяти и командам процессора компьютера фоннеймановской архитектуры.
Как при масштабировании вверх избежать «пословного» рассуждения о программах? (См. речь при присуждении Джону Бэкусу в 1978 г. Тьюринговской премии — John Backus, Can Programming Be Liberated from the von Neumann Style? Turing Award Lecture, 1978).
Нужны приемы, позволяющие определять абстракции высокого уровня (коллекции, многочлены, геометрические фигуры, цепочки символов, документы). В идеале, нужна разработка теорий коллекций, фигур, цепочек...
Каждая такая теория содержит: один или несколько типов данных; операции над этими типами; законы, описывающие отношения между значениями и операциями.
Но теории обычно не описывают изменение значений! Например, теория многочленов определяет сумму двух многочленов посредством таких законов, как:
(a*x + b) + (c*x + d) = (x+c)*x + (b+d)
Но она не определяет оператора изменения коэффициента в одном и том же многочлене!
Или, теория цепочек определяет операцию конкатенации как ассоциативную:
(a ++ b) ++ c = a ++ (b ++ c)
но не оператор, изменяющий ту же самую последовательность.
Сосредоточимся на определении теорий операций; минимизируем изменения состояния; будем рассматривать операции как функции (зачастую состоящие из более простых функций).
Функциональное программирование (ФП) в узком смысле означает программирование без изменяемых переменных, присваиваний, циклов и других императивных управляющих структур. В широком смысле — это программирование, сосредоточенное на функциях. В частности, функции могут выступать в качестве порождаемых, используемых и сочетаемых значений. Функциональные языки это упрощают.
Языки функционального программирования (ЯФП) в узком смысле — это языки, не обладающие изменяемыми переменными, присваиваниями и императивными управляющими структурами.
ЯФП в широком смысле позволяет строить изящные программы, сосредоточенные на функциях. В частности, функции выступают как полноправные значения, которые могут определяться где угодно (в том числе, внутри других функций); передаваться в качестве параметров и возвращаться в качестве результатов других функций; подвергаться композиции.
Примерами ЯФП в узком смысле выступают чистый лисп, XSLT, XPath, XQuery, FP, хаскелл (без монад в/в и UnsafePerformIO). Примеры ЯФП в широком смысле: лисп, схема, рекит, кложа; SML, окамл, F# ; хаскелл (целиком); скала; смолток, руби.
История ЯФП:
1959 | лисп |
1975-77 | МЛ, FP, схема |
1978 | смолток |
1986 | стандартный МЛ |
1990 | хаскелл, эрланг |
1999 | XSLT |
2000 | окамл |
2003 | скала, XQuery |
2005 | F# |
2007 | кложа |
Классический учебник ФП: Harold Abelson and Gerald J. Sussman. Structure and Interpretation of Computer Programs. 2nd edition. MIT Press 1996.
Книги по скале: Martin Odersky, Lex Spoon, Bill Venners.Programming in Scala. 2nd edition. Artima 2010; Scala for the Impatient .
Растущая популярность скалы обусловлена привлекательной методикой задействования параллелизма при многоядерных и облачных вычислениях (Подробнее смотри доклад на 2011 Oscon Java: Working Hard to Keep it Simple).
Применение интерпретатора скалы как калькулятора:
scala> 87 + 145
res0: Int = 232
scala> def size = 2 // определение функции без параметров
size: Int // тип определенной выше функции
scala> 5 * size
res1: Int = 10
(Непримитивное) выражение вычисляется (сводится к значению) так:
1) Берется самая левая операция
2) Вычисляются ее операнды (слева направо)
3) Операция применяется к операндам
[4) Операция с операндами заменяется полученным значением]
Эта процедура применяется, пока не получится значение (в данном примере значение это число).
(2 * pi) * radius
→ (2 * 3.14159) * radius
→ 6.28318 * radius
→ 6.28318 * 10
→ 62.8318
Определяемые функции могут иметь параметры:
scala> def square(x: Double) = x * x
square: (Double)Double
scala> square(2)
res1: Double = 4.0
scala> square(5 + 4)
res2: Double = 81.0
scala> square(square(4))
res3: Double = 256.0
def sumOfSquares(x: Double, y: Double) = square(x) + square(y)
sumOfSquares: (Double,Double)Double
Параметры снабжаются указанием типа. Некоторые примитивные типы:
Int // 32-битные целые
Double // 64-битные с плавающей точкой
Boolean // логические значения (true и false)
Вхождение в выражение параметризованной функции вычисляется (сводится к значению) так же, как операция.
sumOfSquares(3, 2+2)
→ sumOfSquares(3, 4)
→ square(3) + square(4)
→ 3 * 3 + square(4)
→ 9 + square(4)
→ 9 + 4 * 4
→ 9 + 16
→ 25
Модель сведения к значению позволяет строго рассуждать о выражениях, если они не влекут побочных эффектов, и формализуется λ-исчислением, являющимся теоретическим основанием функционального программирования.
Не всякое выражение может быть вычислено (сведено к значению):
def loop: Int = loop
→ loop
→ loop
→ …
Выше приведен пример вызова функции с параметрами по значению. Если параметр функции определен с указанием перед ним «⇒», функция будет вычисляться с параметрами по имени:
scala> def sumOfSquares(x: ⇒ Double, y: ⇒ Double) = square(x) + square(y)
sumOfSquares: (x: => Double, y: => Double)Double
scala> sumOfSquares(3, 2+2)
→ square(3) + square(2+2)
→ 3 * 3 + square(2+2)
→ 9 + square(2+2)
→ 9 + (2+2) * (2+2)
→ 9 + 4 * (2+2)
→ 9 + 4 * 4
→ 25
При отсутствии побочных эффектов и вычислимости всех параметров функция в итоге сводится к одному значению. Однако производительность вычислений может отличаться (если один из параметров не используется).
Если при вызове параметров по значению (ВПЗ) вычисление завершается, то оно завершится и при их вызове по имени (ВПИ). Обратное неверно.
Например, при «def first(x: ⇒ Int, y: ⇒ Int) = x» «first(1, loop)» завершится, а при «def first(x: Int, y: Int) = x» — нет.
Условные выражения используются для выбора между двумя альтернативами. Например:
def abs(x: Int) = if (x >= 0) x else -x
«x >= 0 » здесь выступает предикатом, предикат имеет тип Boolean . Скобки вокруг предиката в скале опускать нельзя.
В логическом выражении могут использоваться:
— константы true и false;
— логические операции отрицание (!b), конъюнкция (b1 && b2), дизъюнкция (b1 || b2) (где b, b1, b2 — логические выражения);
— операции сравнения (e1 <= e2), (e1 >= e2), (e1 < e2), (e1 > e2), (e1 == e2), (e1 != e2 ) (где e1, e2 — выражения численного типа или другие сравнимые).
Сведение логических операций выполняется по следующему правилу:
!true | → | false |
!false | → | true |
true && e | → | e |
false && e | → | false |
true || e | → | true |
false || e | → | e |
Для выполнения конъюнкции и дизъюнкции не всегда нужен правый операнд, иногда они вычисляются с помощью «короткого замыкания».
Задание: Сформулируйте правила сведения для условного выражения:
if (b) e1 then e2
Ответ:
if (true) e1 then e2 → e1
if (b) e1 then e2 → e2
По значению и по имени могут не только передаваться параметры, но и определяться значения.
Определение по имени: «def z = 3+4».
Определение по значению: «val x = 2 ; val y = square(x)».
При определении по значению значение вычисляется в момент определения, например, y из примера выше будет равняться 4, а не square(2).
Разница между val и def выявляется, если справа от знака «=» стоит незавершимое выражение. Например:
def loop: Boolean = loop
def x = loop // Ok
val x = loop // Зациклится
Задание: Напишите «and» и «or» (не пользуясь «&&» и «||»), чтобы имело место соответствие:
and(x, y) == x && y
or(x, y) == x || y
Ответ:
def and(x: Boolean, y: ⇒ Boolean) = if (x) y else false
def or(x: Boolean, y: ⇒ Boolean) = if (x) true else y
def sqrt(x: Double): Double = ...
Классически задача решается последовательным аппроксимированием по методу Ньютона: начинаем с первоначальной догадки об y (например, y = 1) и последовательно улучшаем догадку заменяя ее на среднее арифметическое y и x/y.
1) Определим функцию, вычисляющую один шаг итерации:
def sqrtIter(guess: Double, x: Double): Double =
if (isGoodEnough(guess, x)) guess
else sqrtIter(improve(guess, x), x)
Обратите внимание, что для рекурсивных функций на скале обязательно явное указание типа результата (для нерекурсивных его можно опускать).
Далее,
def improve(guess: Double, x: Double) =
(guess + x / guess) / 2
def isGoodEnough(guess: Double, x: Double) = {
val ε = 0.001
abs(guess * guess - x) < ε}
Тогда:
def sqrt(x: Double) = srqtIter(1.0, x)
Задание: 1) Почему для малых чисел isGoodEnough не слишком точна и может приводить к незавершению для очень больших чисел? 2) Разработайте ее версию, лишенную названных недостатков. 3) Проверьте ее для очень малых и очень больших чисел, например: 0.001 , 0.1e-20 , 1.0e20 , 1.0e50 .
Хорошим стилем в (функциональном) программировании является разбиение задачи на множество небольших функций. Но имена функций, подобных sqrtIter, improve и isGoodEnough имеют значение лишь для реализации, но не для применения функции sqrt. Обычно нам не нужно, чтобы пользователь имел к ним доступ.
Ограничить его и избежать «замусоривания пространства имен» можно, поместив определения вспомогательных функций внутрь определения sqrt:
def sqrt(x: Double) = {
def sqrtIter(guess: Double, x: Double): Double =
if (isGoodEnough(guess, x)) guess
else sqrtIter(improve(guess, x), x)
def improve(guess: Double, x: Double) =
(guess + x / guess) / 2
def isGoodEnough(guess: Double, x: Double) =
abs(square(guess) - x) < 0.001
sqrtIter(1.0, x)
}
Блок выделяется фигурными скобками «{» и «}» и содержит последовательность определений или выражений. Значение блока определяется последним элементом этой последовательности. Этому возвращающему значение выражению могут предшествовать вспомогательные определения. Блоки сами являются выражениями и могут появляться везде, где допустимы выражения. [Имя], определенное внутри блока, видимо только в этом блоке. Определения внутри блока перекрывают определения тех же имен вне блока.
Задание: Чему равно result после выполнения программы:
val x = 0
def f(y: Int) = y + 1
val result = {
val x = f(3)
x * x
} + x
Ответ: 16.
Неперекрытые определения вне блока видны внутри блока. Так что в примере с sqrt мы можем избежать лишней передачи x в качестве параметров вспомогательных функций:
def sqrt(x: Double) = {
def sqrtIter(guess: Double): Double =
if (isGoodEnough(guess)) guess
else sqrtIter(improve(guess))
def improve(guess: Double) =
(guess + x / guess) / 2
def isGoodEnough(guess: Double) =
abs(square(guess) - x) < 0.001
sqrtIter(1.0)
}
Точка с запятой, [соединяющая выражения или инструкции,] в конце строк может опускаться. Если строка содержит более одной инструкции, точка с запятой обязательна.
Соответственно, чтобы записать выражение на нескольких строках, в общем случае лучше заключать его в скобки:
(someLongExpression
+ someOtherExpression)
или следить, чтобы каждая строка, кроме последней, не составляла законченного выражения:
someLongExpression +
someOtherExpression
Так нельзя:
someLongExpression
+ someOtherExpression
Функция f(e1 , ..., en) вызывается посредством вычисления выражений e1,... , en, приводящего к значениям v1, … , vn, последующей замены вызова на тело функции, в котором формальные параметры подменены фактическими параметрами v1, …, vn.
Это можно формализовать как переписывание самой программы:
def f(x1, ..., xn ) = B; ... f(v1, ..., vn )
→
def f(x1, ..., xn ) = B; ... [v1/x1, ..., vn/xn] B
Здесь «[v1/x1, ..., vn/xn] B» означает выражение B, в котором каждое xi заменено на vi.
«[v1/x1, ..., vn/xn] B» называется подстановкой.
Пример переписывания: Рассмотрим функцию вычисления наибольшего общего делителя двух чисел. Вот ее реализация с использованием алгоритма Евклида:
def нод(a: Int, b: Int): Int =
if (b == 0) a else нод(b, a % b)
А вот как она вычисляется:
нод(14, 21)
→ if (21 == 0) 14 else нод(21, 14 % 21)
→ if (false) 14 else нод(21, 14 % 21)
→ нод(21, 14 % 21)
→ нод(21, 14)
→ if (14 == 0) 21 else нод(14, 21 % 14)
→ нод(14, 7)
→
→ нод(7, 0)
→
→ if (0 == 0) 7 else нод(0, 7 % 0)
→ 7
Сравните с переписыванием функции вычисления факториала:
def факт(n: Int): Int =
if (n == 0) 1 else n * факт(n - 1)
факт(4)
→ if (4 == 0) 1 else 4 * факт(4 - 1)
→ 4 * факт(3)
→
→ 4 * (3 * факт(2))
→
→ 4 * (3 * (2 * факт(1)))
→
→ 4 * (3 * (2 * (1 * факт(0)))
→
→ 4 * (3 * (2 * (1 * 1)))
→
→ 120
В чем разница между двумя примерами? — Если функция вызывает себя последним действием, ее кадр стека может быть переиспользован. Это называется хвостовой (или концевой) рекурсией. (В более общем случае, если последнее действие функции заключается в вызове функции (в частности, самой себя), одного кадра стека хватит обеим [экземплярам] функций. Такой вызов называется хвостовым вызовом.)
В скале оптимизируются лишь хвостовые вызовы самой функции (хвостовая рекурсия). Можно явно потребовать хвостовой реализации рекурсивной функции, дав объявление «@tailrec »:
@tailrec
def нод(a: Int, b: Int): Int = ...
При наличии такой аннотации нехвостовая реализация нод приведет к ошибке.
Задание: Придумайте хвостовую реализацию факториала.
В ЯФП функции считаются первоклассными значениями: как и любые другие значения, они могут передаваться в качестве параметров другим функциям и возвращаться ими в качестве результата. Это обеспечивает гибкость при составлении программ. Функции, принимающие в качестве параметра или возвращающие в качестве значения другие функции, называются функциями высокого порядка.
def sumInts(a: Int, b: Int): Int =
// Суммировать все целые от a по b
if (a > b) 0 else a + sumInts(a + 1, b)
def cube(x: Int): Int = x * x * x
def sumCubes(a: Int, b: Int): Int =
// Суммировать кубы всех целых от a по b
if (a > b) 0 else cube(a) + sumCubes(a + 1, b)
def sumфактs(a: Int, b: Int): Int =
// Суммировать факториалы всех целых от a по b
if (a > b) 0 else fact(a) + sumфактs(a + 1, b)
Можно ли обнаружить общую закономерность?
def sum(f: Int ⇒ Int, a: Int, b: Int): Int =
if (a > b) 0
else f(a) + sum(f, a + 1, b)
def sumInts(a: Int, b: Int) = sum(id, a, b)
def sumCubes(a: Int, b: Int) = sum(cube, a, b)
def sumфактs(a: Int, b: Int) = sum(fact, a, b)
def id(x: Int): Int = x
def cube(x: Int): Int = x * x * x
def fact(x: Int): Int = if (x == 0) 1 else fact(x – 1)
Тип A ⇒ B — это тип функции, принимающей аргумент типа A и возвращающей значение типа B.
Функции необязательно определять через def. Можно записывать функциональные литералы (анонимные функции):
(x: Int) ⇒ x * x * x
(x: Int, y: Int) ⇒ x + y
[Фактически, это лямбды]. Анонимная функция «(x1 : T1 , ..., xn : Tn ) ⇒ E» равносильна блоку «{def f(x1 : T1 , ..., xn : Tn ) = E; f }».
Возвращаясь к примеру выше: можно писать вызовы функции высокого порядка с функциональными литералами в качестве параметров-функций:
def sumInts(a: Int, b: Int) = sum(x ⇒ x, a, b)
def sumCubes(a: Int, b: Int) = sum(x ⇒ x * x * x, a, b)
Задания: Напишите функцию умножения, вычисляющую произведение значений некоторой функции в определенных [целых] точках заданного интервала. Запишите факториал в терминах умножения. Можно ли записать еще более общую функцию, обобщающую произведение и сумму?
В функциях суммирования:
def sumInts(a: Int, b: Int) = sum(x ⇒ x, a, b)
def sumCubes(a: Int, b: Int) = sum(x ⇒ x * x * x, a, b)
def sumFactorials(a: Int, b: Int) = sum(fact, a, b)
a и b передаются из sumInts и sumCubes в sum неизменными. От этих параметров можно избавиться. Переопределим sum:
def sum(f: Int ⇒ Int): (Int, Int) ⇒ Int = {
def sumF(a: Int, b: Int): Int =
if (a > b) 0
else f(a) + sumF(a + 1, b)
sumF
}
Теперь sum возвращает другую функцию. Возвращаемая функция принимает два параметра и суммирует результаты применения к каждому из них функции f.
Теперь переопределим:
def sumInts = sum(x ⇒ x)
def sumCubes = sum(x ⇒ x * x * x)
def sumFactorials = sum(fact)
Эти функции можно вызывать как любые другие:
sumCubes(1, 10) + sumFactorials(10, 20)
В этом примере от опосредующих функций можно избавиться, напр.:
sum (cube) (1, 10)
[Можно избавиться и от cube:
sum (x ⇒ x * x * x) (1, 10) ]
Для определения функций, подобных sum из примера выше, в скале есть особый сокращенный синтаксический оборот:
def sum(f: Int ⇒ Int)(a: Int, b: Int): Int =
if (a > b) 0 else f(a) + sum(f)(a + 1, b)
Или, в общем случае, если n > 1:
def f(args1)...(argsn) = E
эквивалентно
def f(args1)...(argsn−1) = {def g(argsn) = E; g}
где g новый идентификатор. или, короче:
def f(args1)...(argsn−1) = (argsn ⇒ E)
Повторяя эту процедуру, можно показать, что:
def f(args1)...(argsn−1)(argsn) = E
эквивалентно:
def f = (args1 ⇒ (args2 ⇒ ...(argsn ⇒ E)...))
Такой стиль определения и вызова фунций называется «каррированием» (в честь логика Х. Б. Карри (1900–82) , популяризовавшего идеи М. Шейнфинкеля и Г. Фреге).
Вопрос: Каков тип функции «def sum(f: Int => Int)(a: Int, b: Int): Int = ... »?
Ответ: (Int => Int) => (Int, Int) => Int .
Обратите внимание, что функциональные типы группируются справа, т. е. Int => Int => Int эквивалентно Int => (Int => Int) .
Задание: Функция sum выше линейно-рекурсивна. Напишите ее хвостовую реализацию, заменив в нижеследующем «???»:
def sum(f: Int => Int)(a: Int, b: Int): Int = {
def loop(a: Int, acc: Int): Int = {
if (???) ???
else loop(???, ???)
}
loop(???, ???)
}
Число x называется неподвижной точкой функции f, если f(x) = x. Неподвижные точки некоторых функций можно найти, начав с предварительной догадки и последовательно применяя f: x, f(x), f(f(x)), f(f(f(x))), ... , пока значение не перестанет изменяться (или его изменения не станут достаточно малы).
Из чего следует такое определение функции поиска неподвижной точки:
val ε = 0.0001
def isCloseEnough(x: Double, y: Double) =
abs((x - y) / x) / x < ε
def fixedPoint(f: Double => Double)(firstGuess: Double) = {
def iterate(guess: Double): Double = {
val next = f(guess)
if (isCloseEnough(guess, next)) next
else iterate(next)
}
iterate(firstGuess)
}
Специфицировать функцию sqrt можно так: sqrt(x) = числу y такому, что y * y = x. Или, разделив обе стороны уравнения на y: sqrt(x) = числу y такому, что y = x / y. Следовательно, sqrt(x) = фиксированной точке функции (y => x / y) .
Однако,
def sqrt(x: Double) = fixedPoint(y => x / y)(1.0)
не завершается. Трассировка переменной next внутри вспомогательной функции iterate показывает, что она колеблется между 1.0 и 2.0.
Одним из способов предотвратить такие колебания является взятие среднего от двух последовательных значений изначальной последовательности:
def sqrt(x: Double) = fixedPoint(y => (y + x / y) / 2)(1.0)
Теперь на четвертом шаге значение next сходится к 1.4142135623746899 [неплохое приближение к √ 2].
Если раскрыть fixedPoint, [вызванную с указанным параметром], получится функция, схожая с написанной нами ранее.
Предыдущие примеры демонстрируют рост выразительности языка при наличии возможности передавать в качестве аргументов функции. Следующий пример покажет, насколько полезной может быть возможность возвращать функции в качестве результата.
Вернемся к поиску неподвижной точки. Мы начали с того, что √x это неподвижная точка функции y => x / y. Затем итерация сошлась за счет усреднения последовательных значений.
Этот прием — стабилизация посредством усреднения — достаточно универсален, чтобы абстрагировать его в отдельную функцию:
def averageDamp(f: Double => Double)(x: Double) = (x + f(x)) / 2
Упражнение: Запишите функцию извлечения квадратного корня с использованием fixedPoint и averageDamp.
Ответ:
def sqrt(x: Double) = fixedPoint(averageDamp(y => x/y))(1.0)
В расширенной нотации Бэкуса—Наура.
Тип = ПростойТип | ФункциональныйТип
ФункциональныйТип = ПростойТип ‘= > ’ Тип | ‘( ’ [ Типы ] ‘) ’ ‘= > ’ Type
ПростойТип = Идент
Типы = Тип { ‘ , ’ Тип }
Тип может быть:
•числовым: Int, Double (или Byte, Short, Char, Long, Float);
•логическим Boolean, допускающим значения true и false;
•цепочечным String type;
•функциональным типом, например, Int => Int или (Int, Int) => Int.
Другие формы типов будут рассмотрены позже.
Выраж = ИнфиксВыраж | ФункцВыраж | if ‘( ’ Выраж ‘) ’ Выраж else Выраж
ИнфиксВыраж = ПрефиксВыраж | ИнфиксВыраж Операц ИнфиксВыраж
Операц = идент
ПрефиксВыраж = [ ‘+ ’ | ‘-’ | ‘! ’ | ‘~ ’ ] ПростВыраж
ПростВыраж = идент | литерал | ПростВыраж ‘. ’ идент | Блок
ФункцВыраж = Привязки ‘= > ‘ Выраж
Привязки = идент [ ‘: ’ ПростТип ] | ‘( ’ [ Привязка { ‘ , ’ Привязка }] ‘) ’
Привязка = идент [ ‘: ’ Тип ]
Блок = ‘{ ’ { Опред ‘; ’} Выраж ‘} ’
Выражение может быть:
•идентификатором, напр. «x», «isGoodEnough»,
•литералом, напр. «0», «1.0», «”abc”»,
•вызовом функции, напр. «sqrt(x)»,
•вызовом операции, напр. «-x», «y + x»,
•выбором (селекцией) [метода], напр. «math.abs»,
•условным выражением, напр. «if (x < 0) -x else x»,
•блоком, напр. «{ val x = math.abs(y) ; x * 2 }» ,
•анонимной функцией, напр. «x => x + 1».
Опред = ОпредФун | ОпредЗнач
ОпредФун = def идент { ‘( ’ [ Параметры ] ‘) ’} [ ‘: ’ Тип ] ‘= ’ Выраж
ОпредЗнач = val идент [ ‘: ’ Тип ] ‘= ’ Выраж
Параметр = идент ‘: ’ [ ‘= > ’ ] Тип
Параметры = Параметр { ‘ , ’ Параметр }
Определение может быть
определением функции, напр. «def square(x: Int) = x * x »,
определением значения, напр. «val y = square(2) ».
Параметр может быть:
параметром, вызываемым по значению, напр. «like (x: Int)» ,
параметром, вызываемым по имени напр, «y: => Double».
Пример: Для рациональных чисел p/q, представленных парой целых p (числителем) и q (знаменателем), определить функцию сложения. Вот класс рациональных:
class Rational(x: Int, y: Int) {
def numer = x
def denom = y
}
Определяется класс и сразу его конструктор. Например, «new Rational(1, 2) » создаст новый объект этого класса, соответствующий числу ½.
numer и denom называются членами объекта класса Rational. К ним можно обращаться посредством инфиксной операции-селектора «.»:
scala> val x = new Rational(1, 2)
x: Rational = Rational@7418e252
scala> x.numer
res2: Int = 1
scala> x.denom
res3: Int = 2
Определим для рациональных функцию сложения и функцию преобразования в цепочку символов:
def addRational(r: Rational, s: Rational): Rational =
new Rational(
r.numer * s.denom + s.numer * r.denom,
r.denom * s.denom)
def makeString(r: Rational) = r.numer + ”/” + r.denom
Тогда:
scala> makeString(addRational(new Rational(1, 2), new Rational(2, 3)))
res4: 7/6
[Зная, что в юникоде есть верхние и нижние индексы и дробная черта, а также предусмотрев смешанный вывод для неправильных дробей, можно реализовать гораздо более красивый вывод рациональных чисел:
def toString = {
def toSuperscript(string:String): String = {
val superscripts =
Map('0' -> '⁰', '1' -> '¹', '2' -> '²', '3' -> '³',
'4' -> '⁴', '5' -> '⁵', '6' -> '⁶', '7' -> '⁷',
'8' -> '⁸', '9' -> '⁹', '+' -> '⁺', '-' -> '⁻')
string.map(c => if (superscripts.isDefinedAt(c))
superscripts(c)
else c)
}
def toSubscript(string:String): String = {
val subscripts =
Map('0' -> '₀', '1' -> '₁', '2' -> '₂', '3' -> '₃',
'4' -> '₄', '5' -> '₅', '6' -> '₆', '7' -> '₇',
'8' -> '₈', '9' -> '₉', '+' -> '₊', '-' -> '₋')
string.map(c => if (subscripts.isDefinedAt(c))
subscripts(c)
else c)
}
(if (numer < 0) "-" else if (numer == 0) "0" else "") +
(if (numer.abs / denom >= 1) (numer.abs / denom).toString else "") +
(if (numer.abs % denom > 0) toSuperscript((numer.abs % denom).toString) +"⁄"+ toSubscript(denom.toString) else "")
}
Это определение требует, чтобы знаменатель был положительным.
scala> new Rational(1, 1)
res0: RationalPackage.Rational = 1
scala> new Rational(-1, 5)
res1: RationalPackage.Rational = -¹⁄₅
scala> new Rational (0, 1)
res2: RationalPackage.Rational = 0
scala> new Rational(2, 3) + new Rational(3, 2)
res3: RationalPackage.Rational = 2¹⁄₆
]
Если такого рода функции включить в определение класса, они будут называться методами:
class Rational(x: Int, y: Int) {
def numer = x
def denom = y
def add(r: Rational) =
new Rational(numer * r.denom + r.numer * denom,
denom * r.denom)
def mul(r: Rational) = ...
...
override def toString = numer.toString + "/" + denom.toString
}
Перед определением toString требуется ключевое слово override, поскольку это определение перекрывает унаследованное от java.lang.Object , [являющегося родительским классом для вновь определяемых классов и объектов по умолчанию].
Методы также могут вызываться посредством инфиксной операции-селектора «.». Параметры им могут передаваться в круглых скобках:
scala> val x = new Rational(1, 3)
x : Rational = 1/3
scala> val y = new Rational(5, 7)
y : Rational = 5/7
scala> val z = new Rational(3, 2)
z : Rational = 3/2
scala> x.add(y).mul(z)
res5: Rational = 66/42
Задания: Дополните определение класса определением метода neg, возвращающего дополнение объекта до нуля. Метода sub для вычисления разности двух рациональных. Чему будет равно x – y – z ?
При так определенном классе рациональные числа не всегда представляются в упрощенном виде. Это легче всего исправить, изменив определение конструктора:
class Rational(x: Int, y: Int) {
private def gcd(a: Int, b: Int): Int =
if (b == 0) a else gcd(b, a % b)
private val g = gcd(x, y)
def numer = x / g
def denom = y / g
...
}
[Собственно, это некорректно для чисел со знаками. Исправить определение можно, например, так:
...
require(d != 0)
private val g = gcd(n.abs, d.abs) * d.signum
// assert(d > 0 && g > 0 || d < 0 && g < 0)
val numer = n / g
val denom = d / g
// assert(denom > 0)
...
]
Ключевое слово «private» перед определениями означает, что область лексической видимости определяемых членов ограничена данным определением класса.
Если ожидается, что методы numer и denom будут вызываться часто, имеет смысл превратить их в значения, например:
class Rational(x: Int, y: Int) {
private def gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)
val numer = x / gcd(x, y)
val denom = y / gcd(x, y)
}
Поведение объектов от этого не изменится. Возможность изменять реализацию без изменения поведения называется абстрагированием данных. Это краеугольный камень в разработке программ.
Внутри определения класса объект, к которому применяется определение, обозначается специальным именем this, напр:
class Rational(x: Int, y: Int) {
...
def less(that: Rational) =
numer * that.denom < that.numer * denom
def max(that: Rational) =
if (this.less(that)) that else this
}
Имя члена того же объекта this.x можно сокращать до x.
Предопределенная функция require принимает предикат и цепочку символов. С ее помощью можно определять предусловия. Например, если требуется, чтобы знаменатель рационального числа был положительным, можно указать:
class Rational(x: Int, y: Int) {
require(y > 0, "знаменатель должен быть положительным")
...
}
Если значение предиката ложно, вызывается исключение недопустимого аргумента (IllegalArgumentException) с заданной цепочкой в качестве параметра.
Подобна ей другая предопределенная функция, assert:
val x = sqrt(y)
assert(x >= 0)
Она при ложности предиката вызывает другое прерывание, прерывание ошибки утверждения (AssertionError), и используется не для проверки предусловий, а проверки хода вычислений в самой программе.
Конструктор, имплицитно определяемый при определении класса, называется первичным конструктором этого класса. Он принимает параметры класса и исполняет все инструкции в теле класса.
Скала допускает определение вторичных конструкторов в виде методов с именем this:
class Rational(x: Int, y: Int) {
def this(x: Int) = this(x, 1)
...
}
scala> new Rational(2)
res6: 2/1
[В данном примере при создании нового объекта с указанием двух параметров будет вызван первичный конструктор, а при указании одного — вторичный конструктор, который, в свою очередь, вызовет первичный.]
Задание: Модифицируйте класс Rational, чтобы внутри объекта рациональные числа сохранялись неупрощенными, но упрощались при преобразовании в строку. Всегда ли поведение таких объектов будет таким же, как объектов изначального класса?
Как вычисляется создание нового экземпляра класса «new C(e1 , ..., em) »? — Аргументы вычисляются подобно аргументам обычной функции, и полученное выражение (например, «new C(v1 , ..., vm)») уже является значением.
Допустим, класс определен так: «class C(x1, ..., xm){ ... def f(y1, ..., yn) = b ... } ». Как будет вычисляться выражение «new C(v1, ..., vm).f(w1, ..., wn) »?
Ответ: Это выражение будет переписано путем трех подстановок:
1) Подстановки аргументов w1, ..., wn вместо формальных параметров функции f (т. е. вместо y1 , ..., yn).
2) Подстановки аргументов класса v1, ..., vm вместо формальных параметров [первичного конструктора] класса C (т. е. вместо x1, ..., xm).
3) Подстановки значения объекта new C(v1 , ..., vn) вместо специального имени this.
new Rational(1, 2).numer
→ [1/x, 2/y] [] [new Rational(1, 2)/this] x
= 1
new Rational(1, 2).less(new Rational(2, 3))
→ [1/x, 2/y] [newRational(2, 3)/that] [new Rational(1, 2)/this]
this.numer * that.denom < that.numer * this.denom
= new Rational(1, 2).numer * new Rational(2, 3).denom <
new Rational(2, 3).numer * new Rational(1, 2).denom
→ 1 * 3 < 2 * 2
→ true
В скале вызов любого метода с параметром можно осуществить, употребив имя этого метода как инфиксную операцию:
r add s ⇔ r.add(s)
r less s ⇔ r.less(s)
r max s ⇔ r.max(s)
[И наоборот, вместо «a + b» можно записать полностью эквивалентное выражение с селектором «a.+(b)»].
В именах можно употреблять не только буквы, но и специальные символы. Например:
class Rational(x: Int, y: Int) {
private def gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)
private val g = gcd(x, y)
def numer = x / g
def denom = y / g
def + (r: Rational) =
new Rational(
numer * r.denom + r.numer * denom,
denom * r.denom)
def - (r: Rational) = ...
def * (r: Rational) = ...
...
}
Тогда можно писать:
scala> new Rational(2)
scala> val x = new Rational(1, 2)
scala> val y = new Rational(1, 3)
x * x + y * y
res8: 13/36
Приоритет операции определяется первым символом ее идентификатора согласно следующему порядку (по возрастанию):
(буква)
|
^
&
< >
= !
:
+ -
* / %
(другой спец. символ)
Задание: Расставьте скобки, соответствующие приоритету операций по умолчанию: «a + b ^? c ?^ d less a ==> b | c».
abstract class IntSet {
def incl(x: Int): IntSet
def contains(x: Int): Boolean
}
Выше определен абстрактный класс. Абстрактные классы, [в отличие от конкретных и от объектов,] могут содержать неопределенные члены (как incl и contains в этом примере). Соответственно, оператором new нельзя создать экземпляра абстрактного класса. Абстрактный класс может выступать только предком других классов.
class Empty extends IntSet {
def contains(x: Int): Boolean = false
def incl(x: Int): IntSet = new NonEmpty(x, new Empty, new Empty)
}
class NonEmpty(elem: Int, left: IntSet, right: IntSet) extends IntSet {
def contains(x: Int): Boolean =
if (x < elem) left contains x
else if (x > elem) right contains x
else true
def incl(x: Int): IntSet =
if (x < elem) new NonEmpty(elem, left incl x, right)
else if (x > elem) new NonEmpty(elem, left, right incl x)
else this
}
Вот два конкретных класса-наследника IntSet. Типы Empty и NonEmpty соответствуют типу IntSet, т. е. если требуется объект типа IntSet, этому требованию удовлетворяет объект любого из этих типов.
IntSet называется надклассом Empty и NonEmpty, а Empty и NonEmpty — подклассами IntSet. В скале любой определяемый класс принадлежит некоторому надклассу, по умолчанию это java.lang.Object.
Ближайший или отдаленный надкласс класса C называется базисным классом C. Таким образом, базисными классами NonEmpty будут IntSet и [java.lang.]Object.
Определения contains и incl из классов Empty и NonEmpty реализуют абстрактные методы их базисного абстрактного класса IntSet.
Существующие неабстрактные определения также можно переопределить («перекрыть») в подклассе, употребляя ключевое слово «override», напр:
abstract class Base {
def foo = 1
def bar: Int
}
class Sub extends Base {
override def foo = 2
def bar = 3
}
В этом примере любые объекты типа Empty были бы одинаковыми, поэтому имеет смысл вместо этого класса определить объект-одиночку:
object Empty extends IntSet {
def contains(x: Int): Boolean = false
def incl(x: Int): IntSet = new NonEmpty(x, Empty, Empty)
}
Упражнение: Напишите метод union для вычисления объединения двух классов. Следует реализовать следующий абстрактный класс:
abstract class IntSet {
def incl(x: Int): IntSet
def contains(x: Int): Boolean
def union(other: IntSet): IntSet
}
Каждая прикладная программа на скале содержит объект с методом main:
object Hello {
def main(args: Array[String]) = println("Здравствуй, мир!")
}
После компиляции такую программу можно запустить посредством команды «scala Hello».
ЯООП (включая скалу) реализуют динамическое назначение методов: программный код, вызываемый при вызове методов, зависит от типа содержащего этот метод объекта во время выполнения.
Примеры:
Empty contains 1
→ [1/x] [Empty/this] false
= false
(new NonEmpty(7, Empty, Empty)) contains 7
→ [7/elem] [7/x] [new NonEmpty(7, Empty, Empty)/this]
if (x < elem) this.left contains x
else if (x > elem) this.right contains x else true
= if (7 < 7) new NonEmpty(7, Empty, Empty).left contains 7
else if (7 > 7) new NonEmpty(7, Empty, Empty).right
contains 7 else true
→ true
Динамическое назначение методов аналогично вызову функций высокого порядка (ФВП).
Вопрос: Могли бы мы реализовать объекты в терминах ФВП? А ФВП в терминах объектов?
Классы и объекты содержатся в пакетах. Для помещения класса или объекта в пакет используйте клаузу «package» в начале своего исходного файла:
package progfun.examples
object Hello { ... }
Затем к объекту Hello можно обращаться (например, чтобы запустить его) по полностью определенному имени: «scala progfun.examples.Hello».
Для обращения можно также использовать «import»: вместо «val r = new week3.Rational(1, 2) » записать:
import week3.Rational
val r = new Rational(1, 2)
Это ключевое слово употребляется в троякой форме:
import week3.Rational // импортируется только Rational
import week3.{Rational, Hello} // импортируются Rational и Hello
import week3._ // импортируется все содержимое пакета week3
Первые две называются импортом по именам, третья — импортом по шаблону. Импорт допустим из пакета или из объекта.
В любую программу на скале автоматически импортируются все члены пакетов scala и java.lang , а также объекта-одиночки scala.Predef . Ниже приведены полностью определенные имена некоторых встречавшихся ранее типов и функций:
Int ⇔ scala.Int
Boolean ⇔ scala.Boolean
Object ⇔ java.lang.Object
require ⇔ scala.Predef.require
assert ⇔ scala.Predef.assert
Стандартную библиотеку скала можно начать изучать со страницы: www.scala-lang.org/api/current
В яве, как и в скале, у класса может быть лишь один надкласс. Чтобы определять классы с несколькими надтипами в скале есть типажи, определяемые аналогично абстрактным классам, [но с ключевым словом «trait»]:
trait Planar {
def height: Int
def width: Int
def surface = height * width
}
Класс, объект или типаж может наследовать лишь одному классу, но произвольному количеству типажей. Например:
class Square extends Shape with Planar with Movable ...
Типажи напоминают явовские интерфейсы, но более мощны, поскольку могут содержать поля и конкретные методы. Но типажи, в отличие от классов, не могут иметь параметров [т. е. у них не может быть ни первичных, ни вторичных конструкторов].
На вершине иерархии скалы:
Any — базисный тип для всех типов. Методы «==», «!=», «equals», «hashCode», «toString».
AnyRef — базисный тип для всех ссылочных типов, синоним «java.lang.Object‘».
AnyVal — базисный тип для всех примитивных типов.
На дне иерархии находится тип Nothing , являющийся подтипом всех остальных типов, Значений этого типа не существует, он полезен для сигнализации о нештатном завершении и как тип элементов пустых коллекций.
Исключения в скала подобны явовским. Выражение «throw Exc» прерывает вычисления с исключением Exc . Исключение возвращает тип Nothing.
Тип Null включает одно значение null, входящее в число допустимых значений любого ссылочного класса. Null является подтипом всех типов, наследующих Object, он несовместим с подтипами anyVal:
scala> val x = null
x: Null = null
scala> val y: String = null
y: String = null
scala> val z: Int = null
<console>:7: error: type mismatch
Вопрос: каков тип выражения «if (true) 1 else false »? Int , Boolean , AnyVal , Object или Any ?
Во многих ЯФП одной из основных структур данных является неизменяемый последовательный список, строящийся из «кирпичиков» двух типов: пустого списка Nil и ячейки Cons, содержащей элемент и [ссылку на] остающуюся часть списка.
Списки целых чисел могут быть представлены такой иерархией классов:
package week4
trait IntList …
class Cons(val head: Int, val tail: IntList) extends IntList …
class Nil extends IntList
Список будет либо пустым списком (создаваемым «new Nil»), либо «new Cons(x, xs)», состоящим из элемента-головы x и списка-хвоста xs.
Сокращение «(val head: Int, val tail: Int)» в определении Cons одновременно определяет параметры [конструктора] и поля класса и эквивалентно:
class Cons(_head: Int, _tail: IntList) extends IntList {
val head = _head
val tail = _tail
}
если _head и _tail больше никак не используются.
Обобщить определение класса можно за счет ти́пового параметра, заключаемого в квадратные скобки:
trait List[T] …
class Cons[T](val head: T, val tail: List[T]) extends List[T] …
class Nil extends List[T]
Полное определение может выглядеть так:
trait List[T] {
def isEmpty: Boolean
def head: T
def tail: List[T]
}
class Cons[T](val head: T, val tail: List[T]) extends List[T] {
def isEmpty = false
}
…
class Nil extends List[T] {
def isEmpty = true
def head = throw new NoSuchElementException("Nil.head")
def tail = throw new NoSuchElementException("Nil.tail")
}
Функции, как и классы, могут иметь ти́повые параметры, например, функция, создающая список из одного элемента:
def singleton[T](elem: T) = new Cons[T](elem, new Nil[T]).
singleton[Int](1)
singleton[Boolean](true)
Обычно скала способна вывести правильный типовый параметр из типов аргументов:
singleton(1)
singleton(true)
Ти́повые параметры в скале присутствуют только во время компиляции, но не во время исполнения, так же как в яве, хаскелле, МЛ и окамле, но в отличие от си++, си# и эф#.
Полиморфизм означает возможность вызывать функцию с аргументами разного типа, а также возможность для типа иметь экземпляры разных типов.
Мы познакомились с двумя основными видами полиморфизма: подтипизацией, при которой экземпляры подкласса передаются базисному классу, и обобщением, при котором экземпляры функции или класса создаются посредством параметризации типа.
Задание: Напишите функцию, принимающую целое n и список и возвращающую n-ный элемент этого списка. Элементы нумеруются с нуля. Если n вне диапазона [0, длина списка – 1], следует вызвать исключение IndexOutOfBoundException.
Скала — чистый объектный язык, т. е. любое значение является объектом. Базовые типы определены в пакете scala (хотя в целях производительности могут использоваться и не чистые реализации). Вот часть определения:
package idealized.scala
abstract class Boolean extends AnyVal {
def ifThenElse[T](t: => T, e: => T): T
def && (x: => Boolean): Boolean = ifThenElse(x, false)
def || (x: => Boolean): Boolean = ifThenElse(true, x)
def unary_!: Boolean
= ifThenElse(false, true)
def == (x: Boolean): Boolean = ifThenElse(x, x.unary_!)
def != (x: Boolean): Boolean = ifThenElse(x.unary_!, x)
...
}
object true extends Boolean {
def ifThenElse[T](t: => T, e: => T) = t
}
object false extends Boolean {
def ifThenElse[T](t: => T, e: => T) = e
}
Задание: Дайте определение операции сравнения < в этом классе (считайте, что false < true ).
Вот частичная реализация класса scala.Int:
class Int {
def + (that: Double): Double
def + (that: Float): Float
def + (that: Long): Long
def + (that: Int): Int // то же для -, *, /, %
def << (cnt: Int): Int // то же для >>, >>>
def & (that: Long): Long
def & (that: Int): Int // то же для |, ^
def == (that: Double): Boolean
def == (that: Float): Boolean
def == (that: Long): Boolean // то же для !=, <, >, <=, >=
...
}
Упражнение: Реализуйте абстрактный класс Nat, представляющий ненегативные целые числа, не пользуясь стандартными численными классами, а реализуя подобъект и подкласс:
object Zero extends Nat
class Succ(n: Nat) extends Nat
— один для нуля, другой для положительных чисел. [Подсказка: «Succ» — от «следующий».]
Функциональные значения в скале являются объектами. Функция типа A => B является сокращением типажа Function1[A, B], определенного так:
package scala
trait Function1[A, B] {
def apply(x: A): B
}
Таким образом, функции — это объекты с методом apply.
Определены также типажи Function2, Function3 … для функций с большим количеством параметров (сейчас — до 22).
Анонимные функции раскрываются (переписываются) так:
(x: Int) => x * x
{ class AnonFun extends Function1[Int, Int] {
def apply(x: Int) = x * x
}
new AnonFun
}
или, в синтаксисе анонимных классов:
new Function1[Int, Int] {
def apply(x: Int) = x * x
}
Вызов функции f(a, b) раскрывается в f.apply(a, b). Таким образом, объектный перевод конструкции:
val f = (x: Int) => x * x
f(7)
будет выглядеть так:
val f = new Function1[Int, Int] {
def apply(x: Int) = x * x
}
f.apply(7 )
Сам по себе метод, например, «def f(x: Int): Boolean = ... », не является функциональным значением, но если так определенная f затем употребляется там, где требуется [значение] функционального типа, она автоматически преобразуется в функциональное значение «(x: Int) => f(x) », или, в развернутом виде, в:
new Function1[Int, Boolean] {
def apply(x: Int) = f(x)
}
Упражнение: Определите в пакете week4 объект object List { ... } с тремя функциями, позволяющими пользователю создавать списки длиной от 0 до 2, используя следующий синтаксис:
List() // пустой список
List(1) // список с одним элементом 1
List(2, 3) // список с двумя элементами 2 и 3.
Двумя основными формами полиморфизма являются подтипизация и обобщения, которые могу использоваться совместно.
Рассмотрим метод assertAllPos, принимающий значение типа IntSet и возвращающий его же, если все элементы множества положительны, а в противном случае вызывающий исключение. Каким должен быть его тип?
— Он может быть любым, соответствующим типу IntSet, т. е. Empty или NonEmpty . Это можно выразить так: «def assertAllPos[S <: IntSet](r: S): S = ... ». «S <: T» означает, что типовый параметр S должен соответствовать T.
И, наоборот, «S >: T» означает, что S должен быть надтипом T, например, спецификация «[S >: NonEmpty] » означает, что типовый параметр S может быть лишь надклассом NonEmpty., т. е. иметь значение NonEmpty, IntSet, AnyRef или Any . [При указании граней предполагается, что каждый тип входит в число собственных подтипов и надтипов.]
В первом случае T называют верхней гранью, а во втором — нижней гранью S. Могут задаваться обе грани одновременно: «[S >: NonEmpty <: IntSet]».
Грань может задаваться также при указании типа переменной.
Из NonEmpty <: IntSet следует List[NonEmpty] <: List[IntSet], и сложные типы, для которых это справедливо, называются ковариантными.
Согласно [одному из следствий из] определения Барбары Лисков, A <: B означает, что действия, допустимые со значениями типа B, допустимы и со значениями типа A. [Т. н. принцип подстановки Лисков, см. Liskov, Barbara; Wing, Jeannette (July 1999). Behavioral Subtyping Using Invariants and Constraints (http://reports-archive.adm.cs.cmu.edu/anon/1999/CMU-CS-99-156.ps)].
В отличие от явы, в скале типизация массивов не ковариантна. В яве с ковариантностью есть проблемы, например:
NonEmpty [] a = new NonEmpty []{ new NonEmpty (1 , Empty , Empty )}
IntSet [] b = a
b [0] = Empty
NonEmpty s = a [0] // переменной непустого значения присваивается пустой массив!
Упражнение: Перепишем последний пример на скале:
val a: Array[NonEmpty] = Array(new NonEmpty(1, Empty, Empty))
val b: Array[IntSet] = a
b(0) = Empty
val s: NonEmpty = a(0)
Что произойдет? Если будет выявлена ошибка типизации, то в какой строке? Или программа скомпилируется без ошибок и вызовет исключение при исполнении? Или исполнится без ошибок.
Ответ: Будет выявлена ошибка типизации при инициализации b (вторая строка).
Грубо говоря, [сложные] типы, допускающие изменение элементов, не должны быть ковариантными, в то время как не допускающие — могут, но при соблюдении некоторых ограничений на методы.
Если C[T] — параметризованный тип и A <: B, между C[A] и C[B] возможны троякого рода отношения: C[A] <: C[B] (C ковариантен), C[A] >: C[B] (C контравариантен) или C[A] и C[B] не являются подтипами друг друга (C инвариантен).
Вариантность типа в скале можно объявить при его определении:
class C[+A] { ... } // С ковариантен
class C1[-A] { ... } // С1 контравариантен
class C2[A] { ... } // С2 инвариантен
Упражнение: Пусть два функциональных типа определены так:
type A = IntSet => NonEmpty
type B = NonEmpty => IntSet
Что из нижеследующего справедливо в соответствии с принципом подстановки Лисков: A <: B , B <: A или A и B не соотносятся?
Обычно функциональные типы подтипизируются следующим образом: если A2 <: A1 и B1 <: B2, то A1 => B1 <: A2 => B2 . Таким образом, функции контравариантны в части типов своих аргументов и ковариантны в части типов своих значений.
Из этого следует такое уточнение определения типажа Function1:
package scala
trait Function1[-T, +U] {
def apply(x: T): U
}
На примере с массивами [из предыдущего параграфа] мы увидели, что ковариантность плохо сочетается с некоторыми операциями, в частности, с операцией изменения значения элемента массива. Если превратить массив в класс, а изменение значения его элемента — в метод:
class Array[+T] {
def update(x: T) ...
}
Проблемы создает сочетание ковариантного ти́пового параметра T с его вхождением в определение метода update.
Компилятор скалы проверит отсутствие такого рода проблем при компиляции класса с объявленной вариантностью. Грубо говоря, ковариантные ти́повые параметры могут входить лишь в [тип] результата методов, контравариантные — только в [типы] параметров методов, а инвариантные — куда угодно. (На самом деле правила чуть сложнее.)
Еще раз:
trait Function1[-T, +U] {
def apply(x: T): U
}
T — контравариантен и встречается только как типовый параметр метода, U — ковариантен и встречается только как тип результата метода. Поэтому определение пройдет проверку при компиляции.
Наша реализация списков имела тот недостаток, что Nil пришлось реализовать как класс, хотя мы бы предпочли, чтобы он был объектом.
Вот как можно это исправить:
trait List[+T] { ... }
object Empty extends List[Nothing] { ... }
Рассмотрим пополнение класса методом prepend, добавляющим в начало списка новый элемент и возвращающим новый список. Казалось бы:
trait List[+T] {
def prepend(elem: T): List[T] = new Cons(elem, this)
}
Но это не сработает!
Вопрос: Почему не проходит ти́повая проверка? — prepend превращает список в изменяемый класс? не проходит проверку на вариантность? правая часть определения содержит ошибку типа?
Ошибкой, разумеется, является нарушение принципа подстановки Лисков. «xs.prepend(Empty)» вполне допустимо, если xs имеет тип List[IntSet] , в то время как та же операция над списком типа List[NonEmpty] привела бы к ошибке типа:
ys.prepend(Empty)
^ type mismatch . required: NonEmpty . found: Empty
Так что List[NonEmpty] — не подтип типа List[IntSet]! Но такой метод нужен для неизменяемых списков!
Вопрос: Как реализовать его корректно с точки зрения вариантности? — Можно указать нижнюю границу: «def prepend [U >: T] (elem: U): List[U] = new Cons(elem, this) ». Тогда проверка на вариантность заверится удачно, ведь ковариантные ти́повые параметры могут появляться в нижней границе типа параметра метода, а контравариантные — в верхней границе типа результата метода.
Упражнение: Реализуйте prepend как указано в типаже List: «def prepend [U >: T] (elem: U): List[U] = new Cons(elem, this) ».
Каков тип результата функции «def f(xs: List[NonEmpty], x: Empty) = xs prepend x »? Не пройдет проверку типов? List[NonEmpty] ? List[Empty] ? List[IntSet] ? List[Any] ?
Напишем простой интерпретатор арифметических выражений, ограниченных числами и сложением. Выражения можно представить иерархией классов с базисным типажом Expr и подклассами Number и Sum. Для обработки выражения необходимо знать его форму и составляющие. Вот реализация:
trait Expr {
def isNumber: Boolean
def isSum: Boolean
def numValue: Int
def leftOp: Expr
def rightOp: Expr
}
class Number(n: Int) extends Expr {
def isNumber: Boolean = true
def isSum: Boolean = false
def numValue: Int = n
def leftOp: Expr = throw new Error("Number.leftOp")
def rightOp: Expr = throw new Error("Number.rightOp")
}
class Sum(e1: Expr, e2: Expr) extends Expr {
def isNumber: Boolean = false
def isSum: Boolean = true
def numValue: Int = throw new Error("Sum.numValue")
def leftOp: Expr = e1
def rightOp: Expr = e2
}
Теперь вычислить выражение можно функцией:
def eval(e: Expr): Int = {
if (e.isNumber) e.numValue
else if (e.isSum) eval(e.leftOp) + eval(e.rightOp)
else throw new Error("Неизвестное выражение " + e)
}
Но записывать такую классификацию и следующие функции быстро надоест! Представьте, что формы выражения расширяются следующими:
class Prod(e1: Expr, e2: Expr) extends Expr // произведение
class Var(x: String) extends Expr // переменная "x"
Придется добавлять в классы методы для классификации и доступа.
Вопрос: сколько новых методов придется определить, чтобы добавить в иерархию эти два класса? 9? 10? 19? 25? 35? 40?
Ответ: 25.
«Хакерским» решением было бы использовать проверку типов и приведение типов — скала позволяет это сделать посредством методов класса Any:
def isInstanceOf[T]: Boolean // проверяет, соответствует ли тип объекта типу T
def asInstanceOf[T]: T // приводит объект к типу T, вызывая исключение «ClassCastException », если это невозможно.
(Это соответствует проверке и приведению типа на яве: «x instanceof T » и «(T) x »). Но применение этих методов на скале не приветствуется, поскольку имеются более привлекательные возможности.
Вот как записывается метод eval с использованием проверок и приведения типов:
def eval(e: Expr): Int =
if (e.isInstanceOf[Number])
e.asInstanceOf[Number].numValue
else if (e.isInstanceOf[Sum])
eval(e.asInstanceOf[Sum].leftOp) +
eval(e.asInstanceOf[Sum].rightOp)
else throw new Error("Неизвестное выражение " + e)
Это исключает необходимость в методах классификации, поскольку обращение к методам происходит лишь для классов, для которых их значение определено. Но это низкоуровневое и потенциально опасное решение.
Например, если нужно лишь вычислять выражения, можно определить:
trait Expr {
def eval: Int
// def show: String // требует определения в классах!
}
class Number(n: Int) extends Expr {
def eval: Int = n
}
class Sum(e1: Expr, e2: Expr) extends Expr {
def eval: Int = e1.eval + e2.eval
}
Если потребуется еще и выводить выражения, придется определять новые методы во всех подклассах!
А если потребуется упрощение выражений, например, по правилу:
a * b + a * c → a * (b + c)
?
Проблема: Это нелокальное упрощение. Его не удастся инкапсулировать в метод одного объекта. Вы опять загнаны в угол: придется проверять и оценивать методы во всех подклассах...
...Итак, мы ищем общий и удобный способ доступа к объектам методами eval, show, simplify... из обширной иерархии классов:
Expr
Number
Sum
Prod
...
Предыдущая попытка привела к квадратичному росту количества методов, применению небезопасных низкоуровневых проверок и приведений типов. Объектно-ориентированная декомпозиция не всегда срабатывает, заставляя при добавлении метода дописывать все классы.
Единственной целью функций проверок и оценок является обращение процесса конструирования [значений]: какого они подкласса? каковы аргументы метода-конструктора?
Это настолько общая задача, что во многих языках, включая скалу, она автоматизирована.
new Sum(e1, e2)
Определение разборного (вариантного) класса подобно определению обычного класса, но ему предшествует модификатор «case», например:
trait Expr
case class Number(n: Int) extends Expr
case class Sum(e1: Expr, e2: Expr) extends Expr
Как и прежде, мы определяем типаж Expr и два конкретных подкласса Number и Sum. При том имплицитно определяются сопутствующие объекты с методом apply:
object Number {
def apply(n: Int) = new Number(n)
}
object Sum {
def apply(e1: Expr, e2: Expr) = new Sum(e1, e2)
}
(Выражение «Number(2)» раскрывается как «Number.apply(2)» и т. п.)
Однако эти классы теперь пусты. Как осуществлять доступ к их членам?
Разбор по шаблону — это обобщение деконструктора «switch» из языков, подобных си или яве, на иерархии классов. На скале он задается ключевым словом «match» [после объекта-селектора]. Например:
def eval(e: Expr): Int = e match {
case Number(n) => n
case Sum(e1, e2) => eval(e1) + eval(e2)
}
За «match» следует последовательность клауз «case pat => exp». Каждому варианту соответствует выражение expr и шаблон pat. Если значению селектора. Если значению селектора не соответствует ни один из шаблонов, вызывается исключение «MatchError». Общая форма:
e match {
case pat1 => expr1
…
case patn => exprn
}
Шаблоны состоят из конструктора (напр. Number или Sum), переменных (напр. n, e1 или e2), универсальных шаблонов «_», констант (напр. 1 или true). Имена констант начинаются с прописной буквы, если это не зарезервированные слова типа null, true, false [и не числа].
Выражение вида:
e match { case p1 => e1 ... case pn => en }
сопоставляет значение селектора e с шаблонами p1 … pn в порядке их записи. Выражение match целиком переписывается в правую часть первой клаузы case, шаблон которой совпал с селектором e. Ссылки на переменные шаблона заменяются при этом на соответствующие части селектора.
Шаблон конструктора C(p1 , ..., pn) соответствует всем значением типа C (или его подтипа), сконструированным с аргументами, совмадающими с p1, ..., pn. Шаблон переменной x соответствует любому значению и связывает имя этой переменной шаблона с данным значением. Шаблон константы c соответствует значению, равному x (в смысле [истинности] операции «==»).
Пример:
eval(Sum(Number(1), Number(2)))
→
Sum(Number(1), Number(2)) match {
case Number(n) => n
case Sum(e1, e2) => eval(e1) + eval(e2)
}
→
eval(Number(1)) + eval(Number(2))
→
Number(1) match {
case Number(n) => n
case Sum(e1, e2) => eval(e1) + eval(e2)
} + eval(Number(2))
→
1 + eval(Number(2))
Разумеется, функцию вычисления [значения выражения] можно теперь определить как метод базисного типажа:
trait Expr {
def eval: Int = this match {
case Number(n) => n
case Sum(e1, e2) => e1.eval + e2.eval
}
}
Упражнение: Напишите с применением поиска по шаблону функцию show, возвращающую строковое представление данного выражения:
def show(e: Expr): String = ???
[Лучше сразу как метод базисного типажа Expr.]
Упражнение повышенной сложности: Добавьте класс Var с переменными x и Prod для произведений x и y, как обсуждалось в лекции и измените функцию show, чтобы она учитывала его. Обратите внимание на правильный приоритет операций при использовании минимального количества скобок, например, «Sum(Prod(2, Var("x")), Var("y")) » должно выводиться как «2 * x + y», но «Prod(Sum(2, Var("x")), Var("y")) » — как «(2 + x) * y».
Список – фундаментальная для функционального программирования структура. Список с элементами x1, … xn записывается «List(x1, … xn)», например:
val fruit = List("яблоки", "апельсины", "груши")
val nums = List(1, 2, 3, 4)
val diag3 = List(List(1, 0, 0), List(0, 1, 0), List(0, 0, 1))
val empty = List()
В отличие от массивов, списки неизменяемы (нельзя присваивать значения его элементам) и рекурсивны (массивы плоски). Как и массивы, списки гомогенны, т. е. все значения должны иметь один тип. Тип списка с элементами типа T обозначается scala.List[T] или просто List[T] :
val fruit : List[String] = List("яблоки", "апельсины", "груши")
val nums : List[Int] = List(1, 2, 3, 4)
val diag3 : List[List[Int]] = List(List(1, 0, 0), List(0, 1, 0), List(0, 0, 1))
val empty : List[Nothing] = List()
Все списки конструируются из пустого списка Nil и операции конструирования «::» (читается «конс»). «x :: xs» создает новый список из элемента x и элементов списка xs:
fruit = "яблоки" :: ("апельсины" :: ("груши" :: Nil))
nums = 1 :: (2 :: (3 :: (4 :: Nil)))
empty = Nil
В скале операции, идентификаторы которых оканчиваются на «:», во-первых, являются методами объекта справа, а не слева от идентификатора операции, а во-вторых, имеют ассоциативность справа налево, а не слева направо. Например, «1 :: 2 :: 3 :: 4 :: Nil » ⇔ «Nil.::(4).::(3).::(2).::(1)» ⇔ «List(1, 2, 3, 4)».
Все операции со списками выразимы в терминах трех следующих операций: head (взятие первого элемента списка — его «головы»), tail (взятие списка, состоящего из всех элементов списка, кроме первого, — его «хвоста»), isEmpty (истина, если список пустой).
Например, для вышеопределенных списков:
fruit.head == "яблоки"
fruit.tail.head == "апельсины"
diag3.head == List(1, 0, 0)
empty.head == throw new NoSuchElementException("голова пустого списка")
Списки можно декомпозировать путем поиска по шаблону:
Nil — константа
p :: ps — шаблон, соответствующий списку с головой p и хвостом ps
List(p1, ..., pn) — то же самое, что и p1 :: ... :: pn :: Nil
Например:
1 :: 2 :: xs | — список, начинающийся с элементов 1 и 2 |
x :: Nil | — список из одного элемента (список длиной 1 ) |
List(x) | — то же, что и x :: Nil |
List() | — пустой список (то же, что и Nil |
Упражнение: Чему равна длина списка, соответствующего шаблону «x :: y :: List(xs, ys) :: zs »? 3? 4? 5? ≥ 3? ≥ 4? ≥ 5?
Предположим, нам нужно отсортировать список чисел в порядке возрастания. Вот один из способов отсортировать «List(7, 3, 9, 2) »: отсортировать его хвост (List(3, 9, 2)) , получив List(2, 3, 9), и вставить голову (7) на нужное место, получив List(2, 3, 7, 9) . Эта идея соответствует сортировке вставкой:
def isort(xs: List[Int]): List[Int] = xs match {
case List() => List()
case y :: ys => insert(y, isort(ys))
}
Упражнение: Завершите определение сортировки вставкой, заполнив поля «???» в следующем определении:
def insert(x: Int, xs: List[Int]): List[Int] = xs match {
case List() => ???
case y :: ys => ???
}
Какова сложность сортировки вставкой в наихудшем случае? O(1)? O(N), O(N log N)? O(N*N)?
Вот методы, часто применяемые к спискам:
xs.length — количество элементов в xs.
xs.last — последний элемент xs (если xs пуст, вызывается исключение).
xs.init — список всех элементов xs, кроме последнего (если xs пуст, вызывается исключение).
xs take n — список первых n элементов xs (или весь xs, если xs.length < n).
xs drop n — список всех элементов xs, кроме первых n [если xs.length <= n, возвращается пустой список].
xs(n) или xs apply n — n-ный элемент xs [элементы нумеруются с нуля, попытка получить элемент n > xs.length – 1 приводит к исключению].
xs ++ ys — список всех элементов xs, за которыми следуют все элементы ys.
xs.reverse — список всех элементов xs в обратном порядке.
xs updated (n, x) — список, содержащий все элементы xs, кроме n-го, который заменяется на x [если xs.length <= n, вызывается исключение].
xs indexOf x — индекс первого элемента xs, равного x, если такой существует, –1 в противном случае.
xs contains x — [истинно, если xs содержит x,] эквивалентно xs indexOf x >= 0.
Сложность метода head представляет собой (небольшую) константу. Какова будет сложность last? Вот возможная реализация last:
def last[T](xs: List[T]): T = xs match {
case List() => throw new Error("последний элемент пустого списка")
case List(x) => x
case y :: ys => last(ys)
}
Получается, что сложность last пропорциональна xs.length.
Упражнение: Реализуйте по аналогии с last внешнюю функцию init :
def init[T](xs: List[T]): List[T] = xs match {
case List() => throw new Error("инициализация пустого списка")
case List(x) => ???
case y :: ys => ???
}
Вот возможная реализация конкатенации (++):
def concat[T](xs: List[T], ys: List[T]) = xs match {
case List() => ys
case z :: zs => z :: concat(zs, ys)
}
Вопрос: Какова ее сложность?
Вот возможная реализация обращения:
def reverse[T](xs: List[T]): List[T] = xs match {
case List() => List()
case y :: ys => reverse(ys) ++ List(y)
}
Вопрос: Какова ее сложность и можно ли ее снизить?
Упражнение: Реализуйте удаление n-ного элемента списка xs (если список короче n, верните сам xs):
def removeAt[T](n: Int, xs: List[T]) = ???
// Пример:
// removeAt(1, List('a', 'b', 'c', 'd'))
// > List(a, c, d)
Упражнение повышенной сложности: Реализуйте уплощение списка (превращение списка, могущего содержать списки списков, списки списки списков и т. д., в список, содержащий элементы всех этих списков).
Идея сортировки слиянием в том, что если список содержит 0 или 1 элемент, он уже отсортирован, а в противном случае можно разделить список примерно пополам, отсортировать каждый из подсписков и слить, [не нарушая порядка], подсписки в один список:
def msort(xs: List[Int]): List[Int] = {
val n = xs.length/2
if (n == 0) xs
else {
def merge(xs: List[Int], ys: List[Int]) = ???
val (fst, snd) = xs splitAt n
merge(msort(fst), msort(snd))
}
}
def merge(xs: List[Int], ys: List[Int]) =
xs match {
case Nil =>
ys
case x :: xs1 =>
ys match {
case Nil =>
xs
case y :: ys1 =>
if (x < y) x :: merge(xs1, ys)
else y :: merge(xs, ys1)
}
}
Функция splitAt [в msort выше] возвращает два списка в виде пары.
Пара является частным случаем кортежа. Кортеж на скала можно записать перечислением его элементов в скобках, например:
scala> val pair = ("answer", 42)
pair: (java.lang.String, Int) = (answer,42)
Типом кортежа (пары) в данном случае будет (java.lang.String, Int).
Кортежи могут использоваться в качестве шаблонов:
scala> val (label, value) = pair
label: java.lang.String = answer
value: Int = 42
Кортежи раскрываются следующим способом: тип кортежа из n элементов (T1, ..., Tn) понимается как сокращенная запись параметризованного типа scala.Tuplen[T1, ..., Tn] . Кортежное выражение (e1, ..., en) эквивалентно вызову функции scala.Tuplen(e1, ..., en). Кортежный шаблон (p1, ..., pn) эквивалентеншаблону конструктора scala.Tuplen(p1, ..., pn).
Кортежные классы понимаются следующим образом (для двоек):
case class Tuple2[T1, T2](_1: +T1, _2: +T2) {
override def toString = "(" + _1 + "," + _2 +")"
}
Члены (поля) кортежа можно адресовать с помощью «_1», «_2» и т. п., так что вместо связки через шаблон «val (label, value) = pair » можно написать:
val label = pair._1
val value = pair._2
Стилистически предпочтительной остается шаблонная форма.
Упражнение: ранее приведенная функция merge записана с помощью вложенного шаблона. Перепишите ее с использованием сравнения с шаблоном пары:
def merge(xs: List[Int], ys: List[Int]): List[Int] =
(xs, ys) match {
???
}
Как можно параметризовать сортировку слиянием, чтобы ее можно было применять не только к спискам целых чисел, но и к спискам элементов другого типа? Просто указать тип в качестве параметра недостаточно, т. к. операция сравнения < определена не для всех типов. Так что придется параметризовать ее с использованием необходимой функции сравнения.
Наиболее гибким образом это можно сделать за счет полиморфности сортировки и передачи ей функции сравнения в качестве дополнительного параметра:
def msort[T](xs: List[T])(lt: (T, T) => Boolean) = {
...
merge(msort(fst)(lt), msort(snd)(lt))
}
Тогда в merge применение < следует заменить вызовом lt:
def merge(xs: List[T], ys: List[T]) = (xs, ys) match {
...
case (x :: xs1, y :: ys1) =>
if (lt(x, y)) ...
else ...
}
Теперь msort можно вызывать так:
val xs = List(-5, 6, 3, 2, 7)
val fruit = List("яблоко", "груша", "апельсин", "ананас")
merge(xs)((x, y) => x < y)
merge(fruit)((x: String, y: String) => x.compareTo(y) < 0)
[В данном случае, разумеется, сработала бы и оригинальная функция, поскольку x < y эквивалентно x.compareTo(y) < 0.]
В стандартной библиотеке уже определен класс, представляющий упорядочение, scala.math.Ordering[T] . С его помощью можно сравнивать элементы типа T. Так что вместо явной параметризации функции msort параметром lt можно параметризовать ее посредством значения Ordering:
def msort[T](xs: List[T])(ord: Ordering) =
def merge(xs: List[T], ys: List[T]) =
... if (ord.lt(x, y)) ...
... merge(msort(fst)(ord), msort(snd)(ord)) ...
Теперь msort можно вызывать так:
import math.Ordering
msort(nums)(Ordering.Int)
msort(fruits)(Ordering.String)
Это заставляет функцию использовать в качестве параметра предопределенные в указанном классе функции, что обеспечивает правильное упорядочение целых и цепочек.
Чтобы не передавать эту функцию каждый раз в явном виде, можно записать ее как имплицитный параметр:
def msort[T](xs: List[T])(implicit ord: Ordering) =
def merge(xs: List[T], ys: List[T]) =
... if (ord.lt(x, y)) ...
... merge(msort(fst), msort(snd)) ...
Теперь можно вызывать msort, не указывая этого параметра явно:
msort(nums)
msort(fruits)
Функция, принимающая имплицитный параметр типа T, будет искать имплицитное (помеченное использованием ключевого слова implicit) определение, имеющее тип, совместимый с T и видимое в точке вызова функции, или же определенное в сопутствующем T объекте. В качестве фактического аргумента, подставляемого вместо имплицитного параметра, будет принято наиболее конкретное такое определение. В противном случае будет выведена ошибка.
[Реально обычно используются либо предопределенные значения Ordering, либо же для вновь определяемого класса это значение определяется в сопутствующем объекте. Если необходимо иметь несколько способов упорядочения значений одного и того же типа, можно определить их в других объектах.]
Вопрос: Какой имплицитный параметр подставляется здесь:
... merge(msort(fst), msort(snd)) ...
Ordering.Int ? Ordering.String ? Параметр ord функции msort”?
Функции над списками часто демонстрируют примеры следующих типовых действий: определенное преобразование каждого элемента списка, получение списка элементов списка, удовлетворяющих определенному критерию, сочетание элементов списка посредством той или иной операции.
Такого рода типовые действия могут программироваться на ЯФП посредством высокопорядковых функций.
Частым типовым действием является преобразование каждого элемента списка и возврат списка результатов; например, чтобы умножить каждый элемент списка на один и тот же множитель, можно написать:
def scaleList(xs: List[Double], factor: Double): List[Double] = xs match {
case Nil => xs
case y :: ys => y * factor :: scaleList(ys, factor)
}
По этому образцу строится обобщенный метод map, упрощенно определяемый так:
abstract class List[T] { ...
def map[U](f: T => U): List[U] = this match {
case Nil => this
case x :: xs => f(x) :: xs.map(f)
}
(реально этот метод определяется сложнее, так как он оптимизирован для хвостовой рекурсии и работает со всеми регулярными типами («коллекциями»), а не только со списками),
Посредством map можно записать scaleList лаконичнее:
def scaleList(xs: List[Double], factor: Double) =
xs map (x => x * factor)
Упражнение: Запишите — сначала без применения метода map, а затем с его применением — функцию, возводящую каждый элемент списка в квадрат и возвращающую список результатов:
def squareList(xs: List[Int]): List[Int] = xs match {
case Nil => ???
case y :: ys => ???
}
def squareList(xs: List[Int]): List[Int] =
xs map ???
Другая частая операция со списками — отбор всех элементов, удовлетворяющих некоторому условию, например:
def posElems(xs: List[Int]): List[Int] = xs match {
case Nil => xs
case y :: ys => if (y > 0) y :: posElems(ys) else posElems(ys)
}
[Вопрос: Что делает эта функция?]
По этому образцу строится обобщенный метод filter, на списках определяемый так:
abstract class List[T] {
...
def filter(p: T => Boolean): List[T] = this match {
case Nil => this
case x :: xs => if (p(x)) x :: xs.filter(p) else xs.filter(p)
}
}
Этот метод позволяет записать posElems лаконичнее:
def posElems(xs: List[Int]): List[Int] =
xs filter (x => x > 0)
У этого метода есть несколько вариаций:
xs filterNot p — эквивалентно (x => !p(x)) , т. е. список состоящий из всех элементов xs, не удовлетворяющих условию p.
xs partition p — эквивалентно (xs filter p, xs filterNot p) , но выполняется за один проход по xs [возвращает пару списков].
xs takeWhile p — самый длинный подсписок-префикс xs), все элементы которого удовлетворяют p.
xs dropWhile p — остаток xs после отбрасывания самого длинного подсписка-префикса, все элементы которого удовлетворяют p.
xs span p — эквивалент (xs takeWhile p, xs dropWhile p) , но выполняется за один проход по xs [возвращает пару списков].
Упражнение: 1) Напишите функцию pack, упаковывающую последовательные повторяющиеся элементы списка в подсписки. Например,
scala> pack(List("a", "a", "a", "b", "c", "c", "a"))
List(List("a", "a", "a"), List("b"), List("c", "c"), List("a"))
Можно воспользоваться следующей заготовкой:
def pack[T](xs: List[T]): List[List[T]] = xs match {
case Nil => Nil
case x :: xs1 => ???
}
2) С ее помощью напишите функцию encode, кодирующую длину серий в списке. Она должна кодировать n последовательных повторяющихся элемента x парой (n, x), например:
scala> encode(List("a", "a", "a", "b", "c", "c", "a"))
List(("a", 3), ("b", 1), ("c", 2), ("a", 1)).
Еще одна частая операция над списками — сочетание элементов списка посредством той или иной операции, например, суммирование всех его элементов:
def sum(xs: List[Int]): Int = xs match {
case Nil => 0
case y :: ys => y + sum(ys)
}
Она обобщается методом левой редукции (reduceLeft):
List(x1, ..., xn) reduceLeft op = (...(x1 op x2) op ... ) op xn
Так что с использованием этого метода сумму и произведение всех элементов списка xs можно записать так:
def sum(xs: List[Int]) = (0 :: xs) reduceLeft ((x, y) => x + y)
def product(xs: List[Int]) = (1 :: xs) reduceLeft ((x, y) => x * y)
«((x, y) => x * y))» можно сократить как «(_ * _) » — здесь каждое подчеркивание заменяет один формальный параметр слева направо:
def sum(xs: List[Int]) = (0 :: xs) reduceLeft (_ + _)
def product(xs: List[Int]) = (1 :: xs) reduceLeft (_ * _)
Левe. редукцию можно обобщить и далее, до левой свертки (foldLeft). Свертка подобна сведению, но принимает в качестве дополнительного параметра аккумулятор z, возвращаемый при вызове foldLeft с пустым списком параметров:
(List(x1, ..., xn) foldLeft z)(op) = (...(z op x1) op ... ) op xn
Таким образом, сумму и произведение списков можно записать как:
def sum(xs: List[Int]) = (xs foldLeft 0) (_ + _)
def product(xs: List[Int]) = (xs foldLeft 1) (_ * _)
[В терминах теории групп или теории операций вообще в качестве «аккумулятора» z здесь просто нейтральный элемент операции, определяющей последующую функцию.]
Эти два метода для списков можно записать так:
abstract class List[T] { ...
def reduceLeft(op: (T, T) => T): T = this match {
case Nil => throw new Error("Nil.reduceLeft")
case x :: xs => (xs foldLeft x)(op)
}
def foldLeft[U](z: U)(op: (U, T) => U): U = this match {
case Nil => z
case x :: xs => (xs foldLeft op(z, x))(op)
}
}
При применении эти методы развертываются в деревья, склоненные влево.
Им соответствуют две функции, развертывающиеся в деревья, склоненные вправо, foldRight и reduceRight :
List(x1, ..., x{n-1}, xn) reduceRight op = x1 op ( ... (x{n-1} op xn) ... )
(List(x1, ..., xn) foldRight acc)(op) = x1 op ( ... (xn op acc) ... )
def reduceRight(op: (T, T) => T): T = this match {
case Nil => throw new Error("Nil.reduceRight")
case x :: Nil => x
case x :: xs => op(x, xs.reduceRight(op))
}
def foldRight[](z: U)(op: (T, U) => U): U = this match {
case Nil => z
case x :: xs => op(x, (xs foldRight z)(op))
}
Для ассоциативных и коммутативных операций левая и правая свертка дают одинаковый результат, хотя производительность их может различаться. Но иногда применим лишь один из этих методов.
Упражнение: Почему в следующем определении нельзя заменить правую свертку левой:
def concat[T](xs: List[T], ys: List[T]): List[T] =
(xs foldRight ys) (_ :: _)
Не сойдутся типы? Функция не завершится? Результат будет перевернут?
[Дополнительное задание: Таки определите concat через foldLeft.
Ответ:
def concat[T](xs: List[T], ys: List[T]): List[T] =
(ys foldLeft xs) (_ ++ List(_))
]
Определим функцию обращения списка линейной сложности. Идея в том, чтобы воспользоваться левой сверткой:
def reverse[T](xs: List[T]): List[T] = (xs foldLeft z?)(op?)
Остается определить z и op. Попробуем, вычислить их, опираясь на примеры. reverse(Nil) == Nil , следовательно:
Nil
= reverse(Nil)
= (Nil foldLeft z)(op)
= z
Следовательно, z = List().
reverse(List(x)) == List(x)
List(x)
= reverse(List(x))
= (List(x) foldLeft Nil)(op?)
= op?(Nil, x)
Следовательно, op?(Nil, x) = List(x) = x :: List() .
Итак, мы приходим к следующему определению:
def reverse[a](xs: List[T]): List[T] =
(xs foldLeft List[T]())((xs, x) => x :: xs)
Вопрос: Какова сложность приведенной реализации?
Упражнение: Завершите следующие определения основных функций map и length на списках с использованием правой свертки:
def mapFun[T, U](xs: List[T], f: T => U): List[U] =
(xs foldRight List[U]())( ??? )
def lengthFun[T](xs: List[T]): Int =
(xs foldRight 0)( ??? )
Проверим, что конкатенация ассоциативна, а пустой список является ее нейтральным элементом, т. е. что справедливы:
(xs ++ ys) ++ zs = xs ++ (ys ++ zs)
xs ++ Nil = xs
Nil ++ xs = xs
Способ доказательства называется структурной индукцией на списках.
Математическая индукция на натуральных числах требует доказательства базы индукции P для некоторого n и шага индукции: следования из [индуктивного предположения] P(n) P(n+1). Например:
def factorial(n: Int): Int =
if (n == 0) 1 // первая клауза
else n * factorial(n-1) // вторая клауза
Докажем, что для всех n >= 4 factorial(n) >= 2n.
База индукции: n = 4
factorial(4) = 24 >= 16 = power(2, 4)
Шаг индукции: n + 1
factorial(n + 1)
>= (n + 1) * factorial(n) // в силу второй клаузы определения
> 2 * factorial(n) // в силу алгебры
>= 2 * power(2, n) // по индуктивному предположению
= power(2, n + 1) // по определению возведения в степень
При доказательстве мы можем пользоваться шагами редукции как равенствами; это потому что функциональные программы не имеют побочных эффектов. Это свойство называется прозрачностью ссылок (referential transparency. ).
Структурная индукция подобна индукции на натуральных числах. Для доказательства справедливости P(xs) для любого списка xs мы в качестве базы доказываем P(Nil), а затем в качестве шага индукции доказываем, что из P(xs) следует P(x :: xs).
Например, докажем ассоциативность конкатенации, т. е.:
(xs ++ ys) ++ zs = xs ++ (ys ++ zs)
Вспомним определение конкатенации:
def concat[T](xs: List[T], ys: List[T]) = xs match {
case List() => ys
case x :: xs1 => x :: concat(xs1, ys)
}
Оно содержит [в обычных обозначениях] две клаузы:
Nil ++ ys = ys // первая
(x :: xs1) ++ ys = x :: (xs1 ++ ys) // вторая
База индукции: Nil
В левой стороне равенства имеем:
(Nil ++ ys) ++ zs = ys ++ zs // в силу первой клаузы
В правой стороне равенства имеем:
Nil ++ (ys ++ zs) = ys ++ zs // в силу второй клаузы
База индукции доказана.
Шаг индукции: x :: xs
В левой стороне равенства имеем:
((x :: xs) ++ ys) ++ zs
= (x :: (xs ++ ys)) ++ zs // в силу первой клаузы
= x :: ((xs ++ ys) ++ zs) // в силу второй клаузы
= x :: (xs ++ (ys ++ zs)) // в силу индуктивного предположения
В правой стороне равенства имеем:
(x :: xs) ++ (ys ++ zs) = x :: (xs ++ (ys ++ zs)) // в силу второй клаузы
Индуктивный шаг доказан (а с ним и теорема в целом).
Упражнение: Докажите по индукции, что xs ++ Nil = xs.
Сколько уравнений требуется для шага индукции: 2? 3? 4?
Сложнее доказывается обращаемость функции reverse. Вот простое (и неэффективное) ее определение:
Nil.reverse = Nil // первая клауза
(x :: xs).reverse = xs.reverse ++ List(x) // вторая клауза
Докажем, что xs.reverse.reverse = xs .
База индукции тривиальна:
Nil.reverse.reverse
= Nil.reverse // в силу первой клаузы
= Nil // в силу первой же клаузы
Попытка шага индукции:
(x :: xs).reverse.reverse = (xs.reverse ++ List(x)).reverse // в силу второй клаузы
Далее левая часть не преобразуется. В правой части:
x :: xs
= x :: xs.reverse.reverse // по индуктивному предположению
Стороны равенства упрощаются в разные выражения. Не очевидно, что:
(xs.reverse ++ List(x)).reverse = x :: xs.reverse.reverse
Однако, если мы обобщим выражение (пусть ys = xs.reverse), имеем:
(ys ++ List(x)).reverse = x :: ys.reverse
Докажем как лемму по индукции:
База индукции:
(Nil ++ List(x)).reverse // = x :: Nil.reverse
= List(x).reverse // в силу первой клаузы определения конкатенации
= (x :: Nil).reverse // по определению списка
= Nil ++ (x :: Nil) // в силу второй клаузы определения reverse
= x :: Nil // в силу первой клаузы определения конкатенации
= x :: Nil.reverse // в силу первой клаузы определения reverse
Шаг индукции:
((y :: ys) ++ List(x)).reverse // x :: (y :: ys).reverse
= (y :: (ys ++ List(x))).reverse // в силу второй клаузы определения конкатенации
= (ys ++ List(x)).reverse ++ List(y) // в силу второй клаузы определения reverse
= (x :: ys.reverse) ++ List(y) // по индуктивному предположению
= x :: (ys.reverse ++ List(y)) // в силу первой клаузы определения конкатенации
= x :: (y :: ys).reverse // в силу второй клаузы определения reverse
Упражнение (проблема повышенной сложности):
Докажите дистрибутивность map по отношению к конкатенации, т. е. что для любых списков xs, ys и любой [не имеющей побочных эффектов] функции f:
(xs ++ ys) map f = (xs map f) ++ (ys map f)
Воспользуйтесь определением конкатенации и следующим определением map:
Nil map f = Nil
(x :: xs) map f = f(x) :: (xs map f)
Список является примером последовательности, а именно, линейной последовательностью. Доступ к голове списка гораздо быстрее доступа к элементу в его середине или конце.
В скале определена последовательность с линейным временем произвольного доступа, вектор.
[… особенности реализации …]
Векторы конструируются аналогично спискам:
val nums = Vector(1, 2, 3, -88)
val people = Vector(”Bob”, ”James”, ”Peter”)
На векторах определены те же операции, что и на списках, за исключением «::», вместо которой определена пара операций «+:» и «:+», добавляющих элемент в начало и конец вектора, соответственно (обратите внимание, что использование символа «:» в операции указывает на то, что она определена на последовательностях).
Базовым классом для классов List и Vector выступает класс Seq, класс всех последовательностей. Сам класс Seq является подклассом итераблей Iterable:
Iterable
Seq
(String)
(Array)
List
Vector
Range
Set
Map
Массивы (Array) и цепочки (String) поддерживают операции над Seq и могут при необходимости неявно преобразовываться в последовательности, но формально не являются подклассами последовательностей, поскольку импортируются из явы:
scala> val xs: Array[Int] = Array(1, 2, 3)
xs: Array[Int] = Array(1, 2, 3)
scala> xs map (x => 2 * x)
res10: Array[Int] = Array(2, 4, 6)
scala> val ys: String = "Hello world!"
ys: String = Hello world!
scala> ys filter (_.isUpper)
res0: String = H
Еще одной разновидностью последовательностей являются диапазоны (Range). Они представляют собой последовательности равноудаленных целых чисел и конструируются посредством трех операций: to («до» включительно), until («до» исключительно), by («по» — определяет шаг):
scala> val r: Range = 1 until 5
r: Range = Range(1, 2, 3, 4)
scala> val s: Range = 1 to 5
s: Range = Range(1, 2, 3, 4, 5)
scala> 1 to 10 by 3
res1: scala.collection.immutable.Range = Range(1, 4, 7, 10)
scala> 6 to 1 by -2
res2: scala.collection.immutable.Range = Range(6, 4, 2)
[В скале имеются также действительночисловые диапазоны (NumericRange):
scala> 6.0 to 1.0 by -0.5
res4: scala.collection.immutable.NumericRange[Double] = NumericRange(6.0, 5.5, 5.0, 4.5, 4.0, 3.5, 3.0, 2.5, 2.0, 1.5, 1.0)
]
Диапазон считается единым объектом с тремя полями: нижней границей, верхней границей и величиной шага.
Некоторые другие из определенных на последовательностях операций:
xs exists p — истинно, если в xs существует такой элемент x, что истинно p(x), иначе ложно.
xs forall p — истинно, если для всех x из xs истинно p(x), иначе ложно.
xs zip ys — последовательность пар, полученных из соответствующих элементов последовательностей xs и ys: [
scala> Vector(1, 2) zip Vector(3, 4)
res5: scala.collection.immutable.Vector[(Int, Int)] = Vector((1,3), (2,4))
Если длина различна, «лишние» элементы более длинной последовательности игнорируются:
scala> Vector(1, 2) zip Vector(3, 4, 5)
res6: scala.collection.immutable.Vector[(Int, Int)] = Vector((1,3), (2,4))
]
xs.unzip — расщепляет пары из последовательности и образует из их элементов пару последовательностей [(обратная по отношению к zip операция):
scala> (Vector(1, 2) zip Vector(3, 4)) unzip
res4: (scala.collection.immutable.Vector[Int], scala.collection.immutable.Vector[Int]) = (Vector(1, 2),Vector(3, 4))
]
xs.sum — сумма всех элементов числовой последовательности.
xs.product — произведение всех элементов числовой последовательности.
xs.max и xs.min — значение максимального и минимального элементов последовательности [определены для элементов типов, на которых определено сравнение].
Примеры:
Перечислить все сочетания чисел x из диапазона 1..M и y из диапазона 1..N:
(1 to M) flatMap (x => (1 to N) map (y => (x, y)))
Вычислить скалярное произведение двух векторов [в произвольномерном пространстве]:
def scalarProduct(xs: Vector[Double], ys: Vector[Double]): Double =
(xs zip ys).map(xy => xy._1 * xy._2).sum
Альтернативой является применение разбора по шаблону:
def scalarProduct(xs: Vector[Double], ys: Vector[Double]): Double =
(xs zip ys).map{ case (x, y) => x * y }.sum
И вообще, [функция]
{ case p1 => e1 ... case pn => en }
эквивалентна [функции]:
x => x match { case p1 => e1 ... case pn => en }
Упражнение: Число n является простым, если делится только на 1 и само на себя. Как с помощью высокоуровневых функций проверить число на простоту? (Найдите лаконичное решение, игнорируя производительность). [Остаток от целочисленного деления берется в скале операцией «%»: 3 % 2 = 1]
Ответ:
def isPrime(n: Int): Boolean =
(2 until n) forall (d => n % d != 0)
Применение высокопорядковых функций над регулярными типами можно распространить на многие вычисления, обычно реализуемые [при императивном программировании] посредством вложенных циклов.
Пример: Дано положительное цело n. Найти все пары положительных целых (i, j) при 1 <= j < i < n такие, что i + j — простое число. Так, для n = 7: (2, 1), (3, 2), (4, 1), (4, 3), (5, 2), (6, 1), (6, 5).
Естественным будет сгенерировать все пары (i, j) при 1 <= j < i < n и отфильтровать те, сумма чисел в которых проста.
Более подробно: сгенерировать все i от 1 до n исключительно, для каждого i сгенерировать все пары от (i, 1) до (i, i-1) … Их можно сгенерировать, сочетая методы until и map:
scala> val n = 7
n: Int = 7
scala> val xss = (1 until n) map (i =>
| (1 until i) map (j => (i, j)))
xss: scala.collection.immutable.IndexedSeq[scala.collection.immutable.IndexedSeq[(Int, Int)]] = Vector(Vector(), Vector((2,1)), Vector((3,1), (3,2)), Vector((4,1), (4,2), (4,3)), Vector((5,1), (5,2), (5,3), (5,4)), Vector((6,1), (6,2), (6,3), (6,4), (6,5)))
Назовем получившуюся последовательность последовательностей xss. Мы можем скомбинировать все ее подпоследовательности, применив правую свертку с операцией ++:
(xss foldRight Seq[Int]())(_ ++ _)
[Здесь неточность, реально так не получится: xss будет иметь тип IndexedSeq[Any], а нужен Seq[Int]. Так выходит потому, что в качестве нейтрального элемента задана пустая последовательность, выливающаяся в пустой первый элемент первой последовательности. Нужно применить правую редукцию:
(xss.toSeq reduceRight (_ ++ _))
res13: scala.collection.immutable.IndexedSeq[(Int, Int)] = Vector((2,1), (3,1), (3,2), (4,1), (4,2), (4,3), (5,1), (5,2), (5,3), (5,4), (6,1), (6,2), (6,3), (6,4), (6,5))
]
В качестве альтернативы можно применить метод flatten:
scala> xss.flatten
res11: scala.collection.immutable.IndexedSeq[(Int, Int)] = Vector((2,1), (3,1), (3,2), (4,1), (4,2), (4,3), (5,1), (5,2), (5,3), (5,4), (6,1), (6,2), (6,3), (6,4), (6,5))
Можно воспользоваться [распределительным] законом xs flatMap f = (xs map f).flatten . Соответственно, вышеприведенное выражение можно упростить:
scala> (1 until n) flatMap (i =>
(1 until i) map (j => (i, j)))
res14: scala.collection.immutable.IndexedSeq[(Int, Int)] = Vector((2,1), (3,1), (3,2), (4,1), (4,2), (4,3), (5,1), (5,2), (5,3), (5,4), (6,1), (6,2), (6,3), (6,4), (6,5))
Собрав все это в одно выражение, мы можем записать:
scala> (1 until n) flatMap (i =>
(1 until i) map (j => (i, j))) filter ( pair =>
isPrime(pair._1 + pair._2))
res18: scala.collection.immutable.IndexedSeq[(Int, Int)] = Vector((2,1), (3,2), (4,1), (4,3), (5,2), (6,1), (6,5))
Это работает, но у большинства от такого болит голова. Есть ли способ выразить это проще?
Путь persons — список элементов класса Person со следующими полями:
case class Person(name: String, age: Int)
Список [имен] лиц старше 20 лет можно получить так:
for ( p <- persons if p.age > 20) yield p.name
Это эквивалентно:
persons filter (p => p.age > 20) map (p => p.name)
For-выражения подобны циклам их императивных языков, но они возвращают список результатов всех итераций.
Еще два примера. 1) Уже знакомая задача: Дано положительное цело n. Найти все пары положительных целых (i, j) при 1 <= j < i < n такие, что i + j — простое число.
for {
i <- 1 until n
j <- 1 until i
if isPrime(i + j)
} yield (i, j)
2) Напишите вариант встречавшейся выше функции scalarProduct с использованием for:
def scalarProduct(xs: List[Double], ys: List[Double]) : Double =
(for ((x, y) <- xs zip ys) yield x * y).sum
Другим примером регулярных типов в скале выступают множества. Они конструируются аналогично последовательностям:
val fruit = Set(”apple”, ”banana”, ”pear”)
val s = (1 to 6).toSet
На множествах определено большинство операций, определенных на последовательностях:
s map (_ + 2)
fruit filter (_.startsWith == ”app”)
s.nonEmpty
(Список всех поддерживаемых операций доступен в документации на итерабли [и на множества]) .
Принципиальными отличиями множество от последовательностей являются 1) их неупорядоченность; 2) невозможность наличия совпадающих элементов:
s map (_ / 2)
// Set(2, 0, 3, 1)
и 3) важнейшая операция contains:
s contains 5
// true
[На последовательностях она также определена.]
Пример: Задача о размещении ферзей. Требуется разместить на шахматной доске восемь ферзей так, чтобы они не били друг друга. Иными словани, никакие два ферзя не должны находиться на одной горизонтали, вертикали или диагонали.
Решим задачу для любого количества ферзей.
Можно помещать по одному ферзю на каждую горизонталь. Разместив k - 1 ферзей, следует k-ого ферзя разместить на вертикаль, не находящуюся «под ударом» ни одного из уже размещенных.
Можно решить задачу по следующему рекурсивному алгоритму:
Предположим, что мы уже разместили k - 1 ферзей на доске n*n.
Каждое решение представлено списком, содержащим номера вертикалей (от 0 до n-1).
Список упорядочен в обратном порядке: первым идет горизонталь k - 1, затем — k - 2 и т. д.
Множество решений представлено множеством списков, где каждому списку соответствует одно решение.
Для размещения k-ого ферзя мы порождаем все возможные дополнения каждого из решений для k-1 ферзей.
Вот его реализация:
def queens(n: Int) = {
def placeQueens(k: Int): Set[List[Int]] = {
if (k == 0) Set(List())
else
for {
queens <- placeQueens(k - 1)
col <- 0 until n
if isSafe(col, queens)
} yield col :: queens
}
placeQueens(n)
}
Упражнение: Напишите функцию:
def isSafe(col: Int, queens: List[Int]): Boolean
проверяющую, что ферзь, размещенный на указанной вертикали col, не находится под ударом уже размещенных ферзей, заданных queens.
Предполагается, что новый ферзь размещается на следующей доступной горизонтали после уже размещенных (т. е. на горизонтали n - 1).
For-выражения по сути эквивалентны обычным операциям, определяемым в языках запросов к базам данных.
Пример: Допустим, у нас есть БД books, представленная как список книг, описанных значениями класса:
case class Book(title: String, authors: List[String])
val books: List[Book] = List(
Book(title = "Structure and Interpretation of Computer Programs",
authors = List("Abelson, Harald", "Sussman, Gerald J.")),
Book(title = "Introduction to Functional Programming",
authors = List("Bird, Richard", "Wadler, Phil")),
Book(title = "Effective Java",
authors = List("Bloch, Joshua")),
Book(title = "Java Puzzlers",
authors = List("Bloch, Joshua", "Gafter, Neal")),
Book(title = "Programming in Scala",
authors = List("Odersky, Martin", "Spoon, Lex", "Venners, Bill")))
Найти названия книг, фамилия автора которых Bird, можно запросом:
for (b <- books; a <- b.authors if a startsWith "Bird,")
yield b.title
Найти все книги, в названии которых есть слово «Program», можно запросом:
for (b <- books if b.title indexOf "Program" >= 0)
yield b.title
Найти имена всех авторов, участвовавших в написании по крайней мере двух книг, включенных в БД, можно так:
for {
b1 <- books
b2 <- books
if b1 != b2
a1 <- b1.authors
a2 <- b2.authors
if a1
} yield a1
Вопрос: Почему ответ сдублирован? Как этого избежать?
Попытка ответа:
for {
b1 <- books
b2 <- books
if b1.title < b2.title
a1 <- b1.authors
a2 <- b2.authors
if a1 == a2
} yield a1
Задача: Сколько раз будет выведено имя автора, если он опубликовал три книги? 1? 2? 3? Ни одного?
Ответ: Нам следует удалить повторяющихся авторов. Этого можно добиться применением метода distinct:
{ for {
b1 <- books
b2 <- books
if b1.title < b2.title
a1 <- b1.authors
a2 <- b2.authors
if a1 == a2
} yield a1
}.distinct
А еще лучше воспользоваться вместо последовательностей множествами:
val bookSet = books.toSet
for {
b1 <- bookSet
b2 <- bookSet
if b1 != b2
a1 <- b1.authors
a2 <- b2.authors
if a1 == a2
} yield a1
Синтаксис «for» тесно связан с высокопорядковыми функциями map, flatMap и filter. Во-первых, все их можно определить в трминах «for»:
def mapFun[T, U](xs: List[T], f: T => U): List[U] =
for (x <- xs) yield f(x)
def flatMap[T, U](xs: List[T], f: T => Iterable[U]): List[U] =
for (x <- xs; y <- f(x)) yield y
def filter[T](xs: List[T], p: T => Boolean): List[T] =
for (x <- xs if p(x)) yield x
Но на самом деле, это «for» раскрываются компилятором скалы в терминах map, flatMap и ленивой версии filter . Вот схема трансляции, используемая компилятором (ограничимся в генераторах простыми переменными):
1) Простое for-выражение:
for (x <- e1) yield e2
→ e1.map(x => e2 )
2) For-выражение с фильтром f и (возможно, пустой) последовательностью генераторов и фильтров s:
for (x <- e1 if f; s) yield e2
→ for (x <- e1.withFilter(x => f); s) yield e2
(далее продолжается трансляция вновь полученного выражения).
Метод withFilter можно считать разновидностью filter, не порождающей временного списка, а применяемой место этого к последующим вызовам функций map и flatMap.
3) 2) For-выражение с (возможно, пустой) последовательностью генераторов и фильтров s:
for (x <- e1; y <- e2; s) yield e3
→ e1.flatMap(x => for (y <- e2; s) yield e3)
(далее продолжается трансляция вновь полученного выражения).
Пример: Возмем нашу функцию, порождающую пары с простой суммой:
for {
i <- 1 until n
j <- 1 until i
if isPrime(i + j)
} yield (i, j)
→ (1 until n).flatMap(i =>
(1 until i).withFilter(j => isPrime(i+j)) .map(j => (i, j)))
Это почти тот код, с которого мы начали!
Упражнение: Странслируйте в терминах высокопорядковых функций:
for (b <- books; a <- b.authors if a startsWith ”Bird”)
yield b.title
Что интересно, трансляция for-выражений не ограничена лишь списками, последовательностями или регулярными типами вообще, она основана исключительно на [применимости] методов map, flatMap и withFilter.
Это позволяет употреблять их с собственными типами, если определить на них эти три метода. Они полезны для самых разных типов: массивов, итераторов, БД, данных на XML, опционных значений, парсеров и т. п.
Например, books из примера выше могла бы быть не списком, но БД, сохраняемой на каком-либо сервере. Если интерфейсом доступа к этой БД определены три названные функции, мы можем для запросов к БД прибегать к for-выражениям.
На этом основаны каркасы доступа к БД на скале ScalaQuery и Slick, и на подобных идеях основана майкрософтовская LINQ.
Еще одним фундаметальным регулярным типом данных являются словари (map, тж. «ассоциативные массивы»).
Словарь типа Map[Key, Value] — это структура данных, связывающая ключи типа Key со значениями типа Value. Например:
scala> val romanNumerals = Map("I" -> 1, "V" -> 5, "X" -> 10)
romanNumerals: scala.collection.immutable.Map[java.lang.String,Int] = Map(I -> 1, V -> 5, X -> 10)
scala> val capitalOfCountry = Map("US" -> "Washington", "Switzerland" -> "Bern")
capitalOfCountry: scala.collection.immutable.Map[java.lang.String,java.lang.String] = Map(US -> Washington, Switzerland -> Bern)
[Значения не обязаны быть одного конкретного типа:
scala> val нуИСловарь = Map(0 -> 1, 2 -> List(1.0, 1.1), 3 -> "сапоги всмятку")
нуИСловарь: scala.collection.immutable.Map[Int,Any] = Map(0 -> 1, 2 -> List(1.0, 1.1), 3 -> сапоги всмятку)
]
Тип Map[Key, Value] является расширением регулярного типа Iterable[(Key, Value)]. Поэтому словари поддерживают те же операции над регулярными типами, что и другие итерабли, например:
val countryOfCapital = capitalOfCountry map {
case(x, y) => (y, x)
} // Map("Washington" -> "US", "Bern" -> "Switzerland")
Обратите внимание, что имеется в виду итерабль над парой ключ/значение. На самом деле, «ключ -> значение» является синонимом пары (ключ, значение).
Кроме того, Map[Key, Value] является расширением [функционального] типа Key => Value, так что словари могут использоваться так же, как и прочие функции. В частности, словарь можно вызвать с ключом в качестве аргумента:
capitalOfCountry("US") // "Washington"
Вызов словаря с несуществующим ключом приводит к ошибке:
scala> capitalOfCountry("Andorra")
java.util.NoSuchElementException: key not found: Andorra
…
Чтобы обратиться к словарю, не зная заранее, существует ли ключ, можно воспользоваться методом get:
scala> capitalOfCountry get "US"
res4: Option[java.lang.String] = Some(Washington)
scala> capitalOfCountry get "Andorra"
res5: Option[java.lang.String] = None
Результатом операции get является значение опционного типа Option. Он определен следующим образом:
trait Option[+A]
case class Some[+A](value: A) extends Option[A]
object None extends Option[Nothing]
Выражение «map get key» [где map — словарь, а key — ключ] возвращает None, если словарь не содержит данного ключа, и Some(x), если словарь связывает данный ключ со значением x.
Поскольку опционы определяются как вариантные классы, их можно разбирать по шаблону:
scala> def showCapital(country: String) = capitalOfCountry.get(country) match {
case Some(capital) => capital
case None => "missing data"
}
showCapital: (country: String)java.lang.String
scala> showCapital("US")
res12: java.lang.String = Washington
scala> showCapital("Andorra")
res13: java.lang.String = missing data
Опционы также поддерживают довольно многие операции над другими регулярными типами. Попробуйте! [Опцион отнесен к регулярным типам, поскольку, как и последовательность или множество, может, по сути, содержать разное количество элементов базового типа, а именно, ноль элементов или один элемент.]
Двумя характерными для запросов к SQL-СУБД операциями, в дополнение к for-выражениям, являются группировка (groupBy) и сортировка (orderBy).
orderBy на регулярных типах можно выразить посредством методов sortWith и sorted.:
scala> val fruit = List("apple", "pear", "orange", "pineapple")
fruit: List[java.lang.String] = List(apple, pear, orange, pineapple)
scala> fruit sortWith (_.length < _.length) // List("pear", "apple", "orange", "pineapple") // сортировка строк по длине
res14: List[java.lang.String] = List(pear, apple, orange, pineapple)
scala> fruit.sorted // лексикографическая сортировка
res15: List[java.lang.String] = List(apple, orange, pear, pineapple)
Над регулярными типами в скале определена функция groupBy. Она возвращает словарь над регулярным типом в соответствии с дискриминантной функцией, например:
scala> fruit groupBy (_.head)
res16: scala.collection.immutable.Map[Char,List[java.lang.String]] = Map(a -> List(apple), o -> List(orange), p -> List(pear, pineapple))
[Тип дискриминантной функции определяет тип ключа словаря, а ее значения — сами ключи. Значения словаря будут иметь тип исходной последовательности. Другой пример: поделим массив фруктов на фрукты с четным и нечетным количеством букв в названии:
scala> fruit.toArray groupBy (_.length % 2 == 0)
res24: scala.collection.immutable.Map[Boolean,Array[java.lang.String]] = Map(false -> Array(apple, pineapple), true -> Array(pear, orange))
]
Еще пример работы со словарями: Многочлен можно представить как словарь из показателей степени в коэффициенты. Например, x3 − 2x + 5 можно представить как Map(0 -> 5, 1 -> -2, 3 -> 1) .
Основываясь на этой возможности, разработаем класс Polynom, представляющий многочлены в виде словарей.
До сих пор мы рассматривали словари-частичные функции: вызов словаря с несуществующим ключом мог привести к исключению. Есть операция withDefaultValue , дополняющая словарь до всюду определенной функции:
scala> val cap1 = capitalOfCountry withDefaultValue "<unknown>"
cap1: scala.collection.immutable.Map[java.lang.String,java.lang.String] = Map(US -> Washington, Switzerland -> Bern)
scala> cap1("Andorra")
res29: java.lang.String = <unknown>
Писать «Polynom(Map(1 -> 2.0, 3 -> 4.0, 5 -> 6.2)) » довольно неудобно, можем ли мы обойтись без «Map(...) »? При этом количество пар показатель → коэффициент может варьировать! Этого можно достичь, используя [в определении] параметр с повторением:
def Polynom(bindings: (Int, Double)*) =
new Polynom(bindings.toMap withDefaultValue 0)
Polynom(1 -> 2.0, 3 -> 4.0, 5 -> 6.2)
В теле функции Polynom связки видны как значение типа Seq[(Int, Double)].
Итак, класс для многочленов можно определить следующим образом:
class Poly(terms0: Map[Int, Double]) {
def this(bindings: (Int, Double)*) = this(bindings.toMap)
val terms = terms0 withDefaultValue 0.0
def + (other: Poly) = new Poly(terms ++ (other.terms map adjust))
def adjust(term: (Int, Double)): (Int, Double) = {
val (exp, coeff) = term
exp -> (coeff + terms(exp))
}
override def toString =
(for ((exp, coeff) <- terms.toList.sorted.reverse)
yield coeff+"x^"+exp) mkString " + "
}
Упражнение: Напишите реализацию метода «+» не в терминах конкатенации словарей, а в терминах левой свертки:
def + (other: Poly) =
new Poly((other.terms foldLeft ???)(addTerm)
def addTerm(terms: Map[Int, Double], term: (Int, Double)) =
???
Какая из версий более эффективна? С использованием конкатенации? или с использованием свертки?
Задача: Телефонным клавишам соответствуют следующие мнемоники:
val mnemonics = Map(
'2' -> "ABC", '3' -> "DEF", '4' -> "GHI", '5' -> "JKL",
'6' -> "MNO", '7' -> "PQRS", '8' -> "TUV", '9' -> "WXYZ")
Допустим, у вас есть список допустимых слов. Разработайте метод translate такой, что вызов translate(phoneNumber) возвращал бы все фразы, которые могут служить в качестве мнемоники данного телефонного номера. Например, номер «7225247386» должен в качестве одного из элементов множества мнемоник возвращать «Scala is fun».
Этот пример взят из статьи: Lutz Prechelt. An Empirical Comparison of Seven Programming Languages // IEEE Computer 33(10): 23-29 (2000) .
Проверен на ти-си-эль, пайтоне, перле, рексксе, яве, си++ и си. срединное значение длины программы: 100 строк кода для сценарных языков, 200 для прочих.
Итак, неизменяемые регулярные структуры данных скалы:
— просты в использовании: задача решается в несколько шагов
— лаконичны: одно слово заменяет целый цикл
— безопасны: проверка типов действительно хорошо отлавливает ошибки
— быстры: операции над ними оптимизированы и могут распараллеливаться
— универсальны: вокабулярий [методов] распространяется на разные типы.
Все это делает их весьма привлекательным орудием разработки программ.
Структурная индукция не ограничена деревьями, она применима к любым древовидным структурам. Общий принцип индукции таков: чтобы доказать P(t) для всех деревьев t определенного типа:
— докажите, что P(t) для всех листьев l дерева;
— для каждого типа внутреннего узла t с поддеревьями s1, … sn докажите, что из P(s1 ) ∧ ... ∧ P(sn) следует P(t).
Пример: Вспомним определение IntSet:
abstract class IntSet {
def incl(x: Int): IntSet
def contains(x: Int): Boolean
}
object Empty extends IntSet {
def contains(x: Int): Boolean = false
def incl(x: Int): IntSet = NonEmpty(x, Empty, Empty)
}
case class NonEmpty(elem: Int, left: IntSet, right: IntSet) extends IntSet {
def contains(x: Int): Boolean =
if (x < elem) left contains x
else if (x > elem) right contains x
else true
def incl(x: Int): IntSet =
if (x < elem) NonEmpty(elem, left incl x, right)
else if (x > elem) NonEmpty(elem, left, right incl x)
else this
}
Что значит доказать правильность реализации? — Определение и доказательство корректности реализации можно дать, доказав, что она подчиняется определенным законам. В случае с IntSet закона у нас три. Для любых множества s и элементов x и y:
Empty contains x = false
(s incl x) contains x = true
(s incl x) contains y = s contains y // if x != y
(На самом деле, мы можем доказать, что эти три закона исчерпывающим образом определяют желаемый тип данных.) Как их можно доказать?
Утверждение 1: Empty contains x = false.
Доказательство: В соответствии с определением contains в Empty.
Утверждение 2: (s incl x) contains x = true
Доказательство: структурной индукцией на s
База индукции: Empty
(Empty incl x) contains x
→ NonEmpty(x, Empty, Empty) contains x // по определению Empty.incl
→ true // по определению NonEmpty.contains
Шаг индукции: NonEmpty(x, l, r)
(NonEmpty(x, l, r) incl x) contains x
→ NonEmpty(x, l, r) contains x // по определению NonEmpty.incl
→ true // по определению NonEmpty.contains
Шаг индукции: NonEmpty(y, l, r) для y < x
(NonEmpty(y, l, r) incl x) contains x
→ NonEmpty(y, l, r incl x) contains x // по определению NonEmpty.incl
→ (r incl x) contains x // по определению NonEmpty.contains
→ true // по индуктивному предположению
Шаг индукции NonEmpty(y, l, r) для y > x аналогичен.
Утверждение 3: Если x != y, то
(xs incl y) contains x = xs contains x.
Докажем по структурной индукции над s. Предположим, что y < x (парный случай x < y доказывается аналогично).
База индукция: Empty
(Empty incl y) contains x // доказать, что = Empty contains x
→ NonEmpty(y, Empty, Empty) contains x // по определению Empty.incl
→ Empty contains x // по определению NonEmpty.contains
Для определения шага индукции рассмотрим дерево NonEmpty(z, l, r) и пять случаев
1) z = x
2) z = y
3) z < y < x
4) y < z < x
5) y < x < z
Шаг индукции: NonEmpty(x, l, r)
(NonEmpty(x, l, r) incl y) contains x // доказать, что: = NonEmpty(x, l, r) contains x
→ NonEmpty(x, l incl y, r) contains x // по определению NonEmpty.incl
→ true // по определению NonEmpty.contains
→ NonEmpty(x, l, r) contains x // по определению NonEmpty.contains
Шаг индукции: NonEmpty(y, l, r)
(NonEmpty(y, l, r) incl y) contains x
→ NonEmpty(y, l, r) contains x // доказать, что: = NonEmpty(y, l, r) contains x // по определению NonEmpty.incl
Шаг индукции: NonEmpty(z, l, r) при z < y < x
(NonEmpty(z, l, r) incl y) contains x // доказать, что: = NonEmpty(z, l, r) contains x
→ NonEmpty(z, l, r incl y) contains x // по определению NonEmpty.incl
→ (r incl y) contains x // по определению NonEmpty.contains
→ r contains x // по индуктивному предположению
→ NonEmpty(z, l, r) contains x // по определению NonEmpty.contains
Шаг индукции: NonEmpty(z, l, r) при y < z < x
(NonEmpty(z, l, r) incl y) contains x // доказать, что: = NonEmpty(z, l, r) contains x
→ NonEmpty(z, l incl y, r) contains x // по определению NonEmpty.incl
→ r contains x // по определению NonEmpty.contains
→ NonEmpty(z, l, r) contains x // по определению NonEmpty.contains
Шаг индукции: NonEmpty(z, l, r) при y < x < z
(NonEmpty(z, l, r) incl y) contains x // доказать, что: = NonEmpty(z, l, r) contains x
→ NonEmpty(z, l incl y, r) contains x // по определению NonEmpty.incl
→ (l incl y) contains x // по определению NonEmpty.contains
→ l contains x // по индуктивному предположению
→ NonEmpty(z, l, r) contains x // по определению NonEmpty.contains
Рассмотрены все случаи, чем доказано утверждение [3].
Упражнение (повышенной сложности):
Корректность объединения множеств может быть представлена следующим законом:
Утверждение 4:
(xs union ys) contains x = xs contains x || ys contains x
Докажите утверждение 4 посредством структурной индукции над xs.
Мы рассмотрели ряд неизменяемых структур данных, на которых определены мощные операции, в особенности, связанные с комбинаторным поиском. Например, так можно найти второе простое число между 1000 и 10000:
((1000 to 10000) filter isPrime)(1)
Это гораздо лаконичнее, чем рекурсивная запись:
def secondPrime(from: Int, to: Int) = nthPrime(from, to, 2)
def nthPrime(from: Int, to: Int, n: Int): Int =
if (from >= to) throw new Error("простого нет")
else if (isPrime(from))
if (n == 1) from else nthPrime(from + 1, to, n - 1)
else nthPrime(from + 1, to, n)
но с точки зрения производительности выражение ((1000 to 10000) filter isPrime)(1) довольно неудачно; оно ищет все простые числа между 1000 и 10000, а только потом выбирает первые два значения из полученного списка.
Снижение верхней границы помогло бы ускорить счет, но увеличило бы риск того, что второе простое число не будет найдено вовсе.
Но мы можем повысить производительность более короткой программы, прибегнув к следующему трюку:
Не вычислять хвост последовательности, пока он не понадобиться для вычисления результата (а он может и вовсе не понадобиться).
Эта идея реализована в новом классе, классе потоков (Stream). потоки сходны со списками, но их хвост вычисляется только когда потребуется.
Потоки определяются с помощью константы пустого потока Stream.empty и конструктора Stream.cons.
Например:
val xs = Stream.cons(1, Stream.cons(2, Stream.empty))
Их можно также определять подобно другим регулярным структурам скалы, используя объект Stream в качестве фабрики классов:
Stream(1, 2, 3)
Превратить регулярную структуру в поток можно методом toStream:
scala> (1 to 1000).toStream
res37: scala.collection.immutable.Stream[Int] = Stream(1, ?)
Попробуем написать функцию, непосредственно возвращающую поток (lo until hi).toStream :
def streamRange(lo: Int, hi: Int): Stream[Int] =
if (lo >= hi) Stream.empty
else Stream.cons(lo, streamRange(lo + 1, hi))
Сравните с аналогичной функцией, возвращающей список:
def listRange(lo: Int, hi: Int): List[Int] =
if (lo >= hi) Nil
else lo :: listRange(lo + 1, hi)
структура этих функций почти одинакова, но вычисляются они совсем по-разному:
— listRange(start, end) породит и вернет список из end – start элементов.
— streamRange(start, end) вернет один объект типа Stream со в качестве головы. Другие элементы будут вычисляться лишь когда они потребуются.
«Потребуются» означает, что будет вызван [элемент из] хвоста данного потока.
Над потоками определены почти все методы, определенные для списка. Например, чтобы найти второе простое число между 1000 и 10000: ((1000 to 10000).toStream filter isPrime)(1)
[Здесь диапазон преобразуется в поток, к которому последовательно применяются методы filter и apply].
Важным исключением является операция «::», всегда порождающая список, а не поток. Однако имеется альтернативная операция «#::», порождающая поток: x #:: xs == Stream.cons(x, xs) . «#::» может употребляться в выражениях, а также в шаблонах.
Реализация потоков весьма сходна с реализацией списков. вот типаж Stream:
The implementation of streams is quite close to the one of lists.
Here’s the trait Stream:
trait Stream[+A] extends Seq[A] {
def isEmpty: Boolean
def head: A
def tail: Stream[A]
...
}
Как и в случае списков, в терминах этих трех методов могут определяться и все другие.
Реализация потоков конкретизуется в сопутствующем объекте Stream. Вот его первый набросок:
object Stream {
def cons[T](hd: T, tl: => Stream[T]) = new Stream[T] {
def isEmpty = false
def head = hd
def tail = tl
}
val empty = new Stream[Nothing] {
def isEmpty = true
def head = throw new NoSuchElementException("empty.head")
def tail = throw new NoSuchElementException("empty.tail")
}
}
Единственное серьезное отличие между реализациями List и Stream касается tl (второго параметра конструктора Stream.cons ). У потоков это параметр, вызываемый по имени. Именно поэтому второй аргумент Stream.cons не вычисляется при его вызове. Вычисляться он будет каждый раз, когда будет происходить обращение к хвосту объекта типа Stream.
Другие методы над потоками реализуются аналогично их синонимам для списков. Вот, например, фильтр:
class Stream[+T] {
...
def filter(p: T => Boolean): Stream[T] =
if (isEmpty) this
else if (p(head)) cons(head, tail.filter(p))
else tail.filter(p)
}
Упражнение: Ниже приведен вариант функции streamRange.:
def streamRange(lo: Int, hi: Int): Stream[Int] = {
print(lo+" ")
if (lo >= hi) Stream.empty
else Stream.cons(lo, streamRange(lo + 1, hi))
}
Что выведет streamRange(1, 10).take(3).toList ? Ничего? «1»? «1 2 3 »? «1 2 3 4 »? «1 2 3 4 5 6 7 8 9 »?
Предложенная в предыдущем параграфе реализация страдает серьезной проблемой, касающейся производительности: если tail вызывается несколько раз, соответствующий поток каждый раз будет перевычисляться. избежать этого можно, сохраняя результат первого вычисления и переиспользуя его вместо перевычисления.
При чисто функциональном программировании это возможно, поскольку значение выражения одно и то же при каждом вычислении.
Этот прием называется ленивыми вычислениями (в противоположность вычислениям по имени, когда все перевычисляется, и от строгих вычислений обычных параметров и определений val).
На языке хаскел ленивые вычисления применяются по умолчанию; на скале вычисления по умолчанию строги, а задать ленивость вычисления при определении можно с помощью «lazy val»:
lazy val x = выраж
Упражнение: Что будет печататься в качестве побюочного эффекта вычисления expr следующей программой:
def expr = {
val x = { print(”x”); 1 }
lazy val y = { print(”y”); 2 }
def z = { print(”z”); 3 }
z + y + x + z + y + x
}
expr
«zyxzyx »? «xyzz »? «xzyz »? «zyzz »? Что-то другое?
С использованием ленивого хвоста Stream.cons можно реализовать эффективнее:
def cons[T](hd: T, tl: => Stream[T]) = new Stream[T] {
def head = hd
lazy val tail = tl
...
}
Убедиться, что эта реализация потока действительно позволяет избегнуть ненужных вычислений, можно, протрассировав исполнение выражения:
(streamRange(1000, 10000) filter isPrime) apply 1
→ (if (1000 >= 10000) empty // в силу раскрытия streamRange
else cons(1000, streamRange(1000 + 1, 10000))
.filter(isPrime).apply(1)
→ cons(1000, streamRange(1000 + 1, 10000)) // в силу вычисления if
.filter(isPrime).apply(1)
Сократим (streamRange(1000, 10000) filter isPrime) до C1:
C1.filter(isPrime).apply(1)
→ (if (C1.isEmpty) C1
// by expanding filter
else if (isPrime(C1.head)) cons(C1.head, C1.tail.filter(isPrime))
else C1.tail.filter(isPrime))
.apply(1)
→ (if (isPrime(C1.head)) cons(C1.head, C1.tail.filter(isPrime)) // в силу вычисления if
else C1.tail.filter(isPrime))
.apply(1)
→ (if (isPrime(1000)) cons(C1.head, C1.tail.filter(isPrime)) // в силу вычисления head
else C1.tail.filter(isPrime))
.apply(1)
↠ (if (false) cons(C1.head, C1.tail.filter(isPrime)) // в силу вычисления isPrime
else C1.tail.filter(isPrime))
.apply(1)
→ C1.tail.filter(isPrime).apply(1) // в силу вычисления if
↠ streamRange(1001, 10000) // в силу вычисления tail
.filter(isPrime).apply(1)
Последовательность вычислений продолжается так до момента:
↠ streamRange(1009, 10000)
.filter(isPrime).apply(1)
→ cons(1009, streamRange(1009 + 1, 10000)) // в силу вычисления streamRange
.filter(isPrime).apply(1)
Сократим cons(1009, streamRange(1009 + 1, 10000)) до C2.:
C2.filter(isPrime).apply(1)
→ cons(1009, C2.tail.filter(isPrime)).apply(1)
→ if (1 == 0) cons(1009, C2.tail.filter(isPrime)).head // в силу выч. apply
else cons(1009, C2.tail.filter(isPrime)).tail.apply(0)
Assuming apply is defined like this in Stream[T]:
def apply(n: Int): T =
if (n == 0) head
else tail.apply(n-1)
→ cons(1009, C2.tail.filter(isPrime)).apply(1)
// в силу выч. filter
→ if (1 == 0) cons(1009, C2.tail.filter(isPrime)).head // в силу выч. apply
else cons(1009, C2.tail.filter(isPrime)).tail.apply(0)
→ cons(1009, C2.tail.filter(isPrime)).tail.apply(0)
// в силу выч. if
→ C2.tail.filter(isPrime).apply(0)
// в силу выч. tail
→ streamRange(1010, 10000).filter(isPrime).apply(0)
// в силу выч. tail
Далее процесс продолжается до:
→
...
streamRange(1013, 10000).filter(isPrime).apply(0) The process continues until
→
→
...
streamRange(1013, 10000).filter(isPrime).apply(0)
cons(1013, streamRange(1013 + 1, 10000))
.filter(isPrime).apply(0)
// в силу выч. streamRange
Let C3 be a shorthand for cons(1013, streamRange(1013 + 1, 10000).
==
C3.filter(isPrime).apply(0)
↠ cons(1013, C3.tail.filter(isPrime)).apply(0) // в силу выч. filter
→ // в силу выч. apply
1013
Конструируется лишь та часть потока, которую требовалось вычислить.
Поскольку, кроме первого, вычисляются лишь необходимые для получения результата элементы потока, можно работать с бесконечными потоками! Например, вот поток всех целых чисел, начиная с определенного:
def from(n: Int): Stream[Int] = n #:: from(n+1)
Поток всех натуральных чисел [здесь натуральные — начиная с нуля]:
val nats = from(0)
Поток всех кратных четырем:
nats map (_ * 4)
С древности известно «решето Эратосфена», позволяющее находить простые числа. Идея заключается в следующем: начинаем с первого простого числа (2), вычеркиваем все числа, кратные 2 — следующим оставшимся будет простое число 3, — вычеркиваем все кратные 3, — и продолжаем до бесконечности. На каждом шаге первым числом в списке оказывается простое, и мы вычеркиваем все числа, кратные ему.
Вот функция, реализующая эту идею:
def sieve(s: Stream[Int]): Stream[Int] =
s.head #:: sieve(s.tail filter (_ % s.head != 0))
val primes = sieve(Stream.from(2))
Чтобы получить список первых N простых чисел, можно написать:
(primes take N).toList
Ранее примененный нами алгоритм нахождения квадратного корня всегда задействовал для прекращения вычисления проверку isGoodEnough . С помощью потоков мы можем выражать понятие сходящейся последовательности, не беспокоясь о ее завершении:
def sqrtStream(x: Double): Stream[Double] = {
def improve(guess: Double) = (guess + x / guess) / 2
lazy val guesses: Stream[Double] = 1 #:: (guesses map improve)
guesses
}
isGoodEnough можно определить и применить позднее:
def isGoodEnough(guess: Double, x: Double) =
math.abs((guess * guess - x) / x) < 0.0001
sqrtStream(4) filter (isGoodEnough(_, 4))
Упражнение: Рассмотрите два способа выразить бесконечный поток чисел, кратных заданному числу N:
val xs = from(1) map (_ * N)
val ys = from(1) filter (_ % N == 0)
Какой из них вычислит результат быстрее? xs? ys?
Ответ: Первый, поскольку второй породит более плотную последовательность, которую затем будет прореживать посредством фильтра. [???]
[…]
Glass: Int
State: Vector[Int] (one entry per glass)
// Moves:
Empty(glass)
Fill(glass)
Pour(from, to)
Такую сложную задачу можно решить разными способами. Какое представление мы выберем?
Отдельные классы для ходов и путей или иное представление?
Объектно-ориентированные методы или голые структуры данных и функции?
Представленное ниже решение — лишь одно из возможных, и не обязательно кратчайшее.
Поименуйте все, что можно.
Соберите действия в естественные области видимости.
Оставляйте степени свободы для дальнейшей доработки.
Функциональное программирование дает целостный способ записи и методику, основанные на:
— высокопорядковых функциях
— разборных классах и разбору по шаблонам
— неизменяемых регулярных структурах данных
— отказе от изменяемых состояний
— гибкой стратегии вычисления со 1) строгими вычислениями, 2) ленивыми вычислениями и 3) вызовом по имени.
Оно представляет собой полезный для каждого программиста инструментарий и еще один способ рассуждения о программах.
«Шпаргалка» по скале (основанная на сообщении на форуме, оставленном Лореном Пуленом).
«Школа скалы» компании «Twitter».
Региональные группы программистов на скале.
Дневник и бюллетень компании «Typesafe».
Дневники «Скала на этой неделе».
Функциональное программирование и состояния:
— что означает обладать изменяемым состоянием?
— что изменяется с его учетом?
Параллелизм:
— как пользоваться неизменяемостью для распараллеливания исполнения.
Предметно-ориентированные языки:
— высокоуровневые библиотеки как встроенные ПОЯ
— приемы интерпретации внешних ПОЯ.