Scala в примерах: различия между версиями
Содержимое удалено Содержимое добавлено
Annayudi (обсуждение | вклад) |
Annayudi (обсуждение | вклад) →Определение класса List II: методы высшего порядка: — перевод параграфа |
||
Строка 2436:
== Определение класса List II: методы высшего порядка ==
Примеры, которые мы рассмотрели к этому моменту, показывают, что функции работы со списками часто имеют похожие структуры. Мы можем определить несколько шаблонов вычислений со списками, например:
* преобразование каждого элемента списка неким образом,
* выбор из списка всех элементов, удовлетворяющих критерию,
* объединение элементов списка при помощи некого оператора.
Языки функционального программирования позволяют писать общие функции, которые реализуют такие шаблоны при помощи функций высшего порядка. Ниже мы представим множество часто используемых функций высшего порядка, которые реализованы как методы в классе <tt>List</tt>.
<font size=3>'''Отображение для списков'''</font>
Часто встречается операция преобразования каждого элемента списка и затем возврата списка результатов. Например, чтобы умножить каждый элемент списка на данное число:
<font size=3><syntaxhighlight lang=Scala>
def scaleList(xs: List[Double], factor: Double): List[Double] = xs match {
case Nil => xs
case x :: xs1 => x * factor :: scaleList(xs1, factor)
}
</syntaxhighlight></font>
Этот шаблон может быть обобщен до метода <tt>map</tt> класса <tt>List</tt>:
<font size=3><syntaxhighlight lang=Scala>
abstract class List[A] { …
def map[B](f: A => B): List[B] = this match {
case Nil => this
case x :: xs => f(x) :: xs.map(f)
}
</syntaxhighlight></font>
При помощи <tt>map</tt> можно написать <tt>scaleList</tt> более кратко:
<font size=3><syntaxhighlight lang=Scala>
def scaleList(xs: List[Double], factor: Double) =
xs map (x => x * factor)
</syntaxhighlight></font>
Для другого примера рассмотрим задачу возврата данного столбца матрицы, которая представлена списком строк, где каждая строка тоже является списком. Это можно сделать при помощи такой функции <tt>column</tt>:
<font size=3><syntaxhighlight lang=Scala>
def column[A](xs: List[List[A]], index: Int): List[A] =
xs map (row => row(index))
</syntaxhighlight></font>
С <tt>map</tt> тесно связан метод <tt>foreach</tt>, который применяет данную функцию ко всем элементам списка, но не создает список результатов. То есть, функция применяется только ради своих побочных эффектор. <tt>foreach</tt> определяется так:
<font size=3><syntaxhighlight lang=Scala>
def foreach(f: A => Unit) {
this match {
case Nil => ()
case x :: xs => f(x); xs.foreach(f)
}
}
</syntaxhighlight></font>
Эту функцию можно использовать для вывода на экран всех элементов списка, например:
<font size=3><syntaxhighlight lang=Scala>
xs foreach (x => println(x))
</syntaxhighlight></font>
'''Упражнение 9.4.1''' Рассмотри функцию, которая возводит в квадрат все элементы списка и возвращает список с результатами. Закончите следующие два эквивалентных определения <tt>squareList</tt>:
<font size=3><syntaxhighlight lang=Scala>
def squareList(xs: List[Int]): List[Int] = xs match {
case List() => ??
case y :: ys => ??
}
def squareList(xs: List[Int]): List[Int] =
xs map ??
</syntaxhighlight></font>
<font size=3>'''Фильтрация списков'''</font>
Другая частая операция выбирает из списка все элементы, удовлетворяющие данному критерию. Например, чтобы вернуть список всех положительных элементов данного списка целых чисел:
<font size=3><syntaxhighlight lang=Scala>
def posElems(xs: List[Int]): List[Int] = xs match {
case Nil => xs
case x :: xs1 => if (x > 0) x :: posElems(xs1) else posElems(xs1)
}
</syntaxhighlight></font>
Этот шаблон обобщен до метода <tt>filter</tt> класса <tt>List</tt>:
<font size=3><syntaxhighlight lang=Scala>
def filter(p: A => Boolean): List[A] = this match {
case Nil => this
case x :: xs => if (p(x)) x :: xs.filter(p) else xs.filter(p)
}
</syntaxhighlight></font>
При помощи <tt>filter</tt> можно записать <tt>posElems</tt> короче следующим образом:
<font size=3><syntaxhighlight lang=Scala>
def posElems(xs: List[Int]): List[Int] =
xs filter (x => x > 0)
</syntaxhighlight></font>
Операция, имеющая отношение к фильтрации — проверка, удовлетворяют ли все элементы списка некому критерию. Можно также задаться дуальным вопросом, содержится ли в списке элемент, удовлетворяющий некому критерию. Эти операции воплощены в функциях высшего порядка <tt>forall</tt> и <tt>exists</tt> класса <tt>List</tt>.
<font size=3><syntaxhighlight lang=Scala>
def forall(p: A => Boolean): Boolean =
isEmpty || (p(head) && (tail forall p))
def exists(p: A => Boolean): Boolean =
!isEmpty && (p(head) || (tail exists p))
</syntaxhighlight></font>
Чтобы проиллюстрировать, как используется <tt>forall</tt>, рассмотрим вопрос, является ли число простым. Число ''n'' — простое, если оно делится без остатка только на единицу и на самого себя. Самый прямолинейный способ — проверять, равен ли остаток от деления ''n'' на все числа от <tt>2</tt> до ''n'' не включительно нулю. Список чисел может быть сгенерирован при помощи функции <tt>List.range</tt>, которая определена в объекте <tt>List</tt> следующим образом:
<font size=3><syntaxhighlight lang=Scala>
package scala
object List { …
def range(from: Int, end: Int): List[Int] =
if (from >= end) Nil else from :: range(from + 1, end)
</syntaxhighlight></font>
Например, <tt>List.range(2, n)</tt> генерирует список всех целых чисел от <tt>2</tt> до ''n'' не включительно. Функцию <tt>isPrime</tt> теперь можно просто определить так:
<font size=3><syntaxhighlight lang=Scala>
def isPrime(n: Int) =
List.range(2, n) forall (x => n % x != 0)
</syntaxhighlight></font>
Мы видим, что математическое определение простоты может быть прямо переведено в код на Scala.
'''Упражнение.''' Определите <tt>forall</tt> и <tt>exists</tt> при помощи <tt>filter</tt>.
<font size=3>'''Свертки и редукции списков'''</font>
Еще одна частая операция — объединение элементов списка при помощи какого-нибудь оператора. Например,
<code>
sum(List(x<sub>1</sub>, …, x<sub>n</sub>)) = 0 + x<sub>1</sub> + … + x<sub>n</sub><br>
product(List(x<sub>1</sub>, …, x<sub>n</sub>)) = 1 * x<sub>1</sub> * … * x<sub>n</sub>
</code>
Конечно, можно реализовать обе эти функции рекурсивно:
<font size=3><syntaxhighlight lang=Scala>
def sum(xs: List[Int]): Int = xs match {
case Nil => 0
case y :: ys => y + sum(ys)
}
def product(xs: List[Int]): Int = xs match {
case Nil => 1
case y :: ys => y * product(ys)
}
</syntaxhighlight></font>
Но также можно использовать обобщение такой схемы, заключенной в методе <tt>reduceLeft</tt> класса <tt>List</tt>. Этот метод вставляет данный бинарный оператор между последовательными элементами данного списка. Например,
<code>
List(x<sub>1</sub>, …, x<sub>n</sub>).reduceLeft(op) = (…(x<sub>1</sub> op x<sub>2</sub>) op … ) op x<sub>n</sub>
</code>
При помощи <tt>reduceLeft</tt> можно сделать очевидным общий шаблон в <tt>sum</tt> и <tt>product</tt>:
<font size=3><syntaxhighlight lang=Scala>
def sum(xs: List[Int]) = (0 :: xs) reduceLeft {(x, y) => x + y}
def product(xs: List[Int]) = (1 :: xs) reduceLeft {(x, y) => x * y}
</syntaxhighlight></font>
Вот реализация <tt>reduceLeft</tt>:
<font size=3><syntaxhighlight lang=Scala>
def reduceLeft(op: (A, A) => A): A = this match {
case Nil => error("Nil.reduceLeft")
case x :: xs => (xs foldLeft x)(op)
}
def foldLeft[B](z: B)(op: (B, A) => B): B = this match {
case Nil => z
case x :: xs => (xs foldLeft op(z, x))(op)
}
</syntaxhighlight></font>
Мы видим, что метод <tt>reduceLeft</tt> определен при помощи другого общеполезного метода <tt>foldLeft</tt>. Он принимает дополнительным параметром ''аккумулятор'' <tt>z</tt>, который возвращается, когда <tt>foldLeft</tt> применяется к пустому списку. То есть,
<code>
(List(x<sub>1</sub>, …, x<sub>n</sub>) foldLeft z)(op) = (…(z op x<sub>1</sub>) op … ) op x<sub>n</sub>
</code>
Методы <tt>sum</tt> и <tt>product</tt> могут быть определены и при помощи <tt>foldLeft</tt>:
<font size=3><syntaxhighlight lang=Scala>
def sum(xs: List[Int]) = (xs foldLeft 0) {(x, y) => x + y}
def product(xs: List[Int]) = (xs foldLeft 1) {(x, y) => x * y}
</syntaxhighlight></font>
<font size=3>'''FoldRight и ReduceRight'''</font>
Применения <tt>foldLeft</tt> и <tt>reduceLeft</tt> раскрываются в левые деревья. У них есть дуальные <tt>foldRight</tt> и <tt>reduceRight</tt>, которые дают правые деревья.
<code>
List(x<sub>1</sub>, …, x<sub>n</sub>).reduceRight(op) = x<sub>1</sub> op ( … (x<sub>n-1</sub> op x<sub>n</sub>)…)<br>
(List(x<sub>1</sub>, …, x<sub>n</sub>) foldRight acc)(op) = <sub>x1</sub> op ( … (x<sub>n</sub> op acc)…)
</code>
Они определены следующим образом:
<font size=3><syntaxhighlight lang=Scala>
def reduceRight(op: (A, A) => A): A = this match {
case Nil => error("Nil.reduceRight")
case x :: Nil => x
case x :: xs => op(x, xs.reduceRight(op))
}
def foldRight[B](z: B)(op: (A, B) => B): B = this match {
case Nil => z
case x :: xs => op(x, (xs foldRight z)(op))
}
</syntaxhighlight></font>
Класс <tt>List</tt> определяет также две символьных аббревиатуры для <tt>foldLeft</tt> и <tt>foldRight</tt>:
<font size=3><syntaxhighlight lang=Scala>
def /:[B](z: B)(f: (B, A) => B): B = foldLeft(z)(f)
def :\[B](z: B)(f: (A, B) => B): B = foldRight(z)(f)
</syntaxhighlight></font>
Имена методов иллюстрируют левые/правые деревья операции свертки при помощи прямых и обратных слэшей. Двоеточие в каждом случае указывает на список, а конец слэша указывает на аккумулятор <tt>z</tt>. То есть,
<code>
(z /: List(x<sub>1</sub>, …, x<sub>n</sub>)(op) = (…(z op x<sub>1</sub>) op … ) op x<sub>n</sub><br>
(List(x<sub>1</sub>, …, x<sub>n</sub>) :\ z)(op) = x<sub>1</sub> op ( … (x<sub>n</sub> op z)…)
</code>
Для ассоциативных и коммутативных операторов <tt>/:</tt> и <tt>:\</tt> эквивалентны (несмотря на то, что в эффективности могут быть различия).
'''Упражнение 9.4.2''' Рассмотрим задачу написания функции <tt>flatten</tt>, которая принимает список списков элементов в качестве аргументов. Результат <tt>flatten</tt> должен быть конкатенацией всех элементов списков в один список. Ниже приведена реализация этого метода при помощи <tt>:\</tt>.
<font size=3><syntaxhighlight lang=Scala>
def flatten[A](xs: List[List[A]]): List[A] =
(xs :\ (Nil: List[A])) {(x, xs) => x ::: xs}
</syntaxhighlight></font>
Рассмотрим замену тела <tt>flatten</tt> на
<font size=3><syntaxhighlight lang=Scala>
((Nil: List[A]) /: xs) ((xs, x) => xs ::: x)
</syntaxhighlight></font>
Какова будет разница в асимптотической сложности между двумя версиями <tt>flatten</tt>?
На самом деле, <tt>flatten</tt> предопределен вместе со множеством других полезных функций в объекте <tt>List</tt> стандартной библиотеки Scala. Его можно вызвать из пользовательской программы при помощи <tt>List.flatten</tt>. Обратить внимание, что <tt>flatten</tt> не является методом класса <tt>List</tt> — это не имело бы смысла, поскольку он применяется только к спискам списков, а не к спискам вообще.
<font size=3>'''Опять обращение списков'''</font>
В [Scala в примерах#Определение класса List I: методы первого порядка|Параграфе 9.2] мы видели реализацию метода обращения списка <tt>reverse</tt>, квадратичную от длины входа по времени выполнения. Теперь мы разработаем новую реализацию <tt>reverse</tt> линейной сложности. Идея в том, чтобы использовать операцию <tt>foldLeft</tt>, основываясь на следующей схеме:
<font size=3><syntaxhighlight lang=Scala>
class List[+A] { …
def reverse: List[A] = (z? /: this)(op?)
</syntaxhighlight></font>
Остается только заполнить части <tt>z?</tt> и <tt>op?</tt>. Давайте попытаемся вывести их из примеров.
<font size=3><syntaxhighlight lang=Scala>
Nil
= Nil.reverse // по спецификации
= (z /: Nil)(op) // по шаблону для обращения
= (Nil foldLeft z)(op) // по определению /:
= z // по определению foldLeft
</syntaxhighlight></font>
Заметим, что <tt>z?</tt> должен быть <tt>Nil</tt>. Чтобы вывести второй операнд, рассмотрим обращение списка единичной длины.
<font size=3><syntaxhighlight lang=Scala>
List(x)
= List(x).reverse // по спецификации
= (Nil /: List(x))(op) // по шаблону для обращения с z = Nil
= (List(x) foldLeft Nil)(op) // по определению /:
= op(Nil, x) // по определению foldLeft
</syntaxhighlight></font>
Следовательно, <tt>op(Nil, x)</tt> равно <tt>List(x)</tt>, которое равно <tt>x :: Nil</tt>. То есть, можно взять в качестве op оператор <tt>::</tt>, поменяв местами его операнды. Следовательно, у нас получается следующая реализация <tt>reverse</tt>, и ее сложность линейна:
<font size=3><syntaxhighlight lang=Scala>
def reverse: List[A] =
((Nil: List[A]) /: this) {(xs, x) => x :: xs}
</syntaxhighlight></font>
(Аннотация типа <tt>Nil</tt> необходима, чтобы обеспечить корректную работу системе вывода типов.)
'''Упражнение 9.4.3''' Вставьте пропущенные выражения, чтобы закончить следующие определения некоторых базовых операций со списками:
<font size=3><syntaxhighlight lang=Scala>
def mapFun[A, B](xs: List[A], f: A => B): List[B] =
(xs :\ List[B]()){ ?? }
def lengthFun[A](xs: List[A]): int =
(0 /: xs){ ?? }
</syntaxhighlight></font>
<font size=3>'''Вложенные отображения'''</font>
Мы можем использовать функции высшего порядка для работы со списками, чтобы выразить многие вычисления, которые обычно выражаются при помощи вложенных циклов в императивных языках.
Для примера рассмотрим следующую задачу: дано положительное целое число ''n'', найти все пары положительных чисел ''i'' и ''j'', где <tt>1 ≤ j < i < n</tt>, таких что ''i + j'' — простое число. Например, если ''n = 7'', то пары таковы:
{| class="wikitable"
|''i''
|2
|3
|4
|4
|5
|6
|6
|-
|''j''
|1
|2
|1
|3
|2
|1
|5
|-
|''i + j''
|3
|5
|5
|7
|7
|7
|11
|}
Естественный путь решения этой задачи состоит из двух частей. На первом шаге сгенерируем последовательность всех пар целых чисел ''(i, j)'', таких что <tt>1 ≤ j < i < n</tt>. На втором шаге отфильтруем из этой последовательности все пары ''(i, j)'', такие что ''i + j'' — простое число.
Посмотрим на первый шаг более детально. Естественный способ генерации последовательности пар состоит из трех подпунктов. Во-первых, сгенерируем все целые числа от <tt>1</tt> до ''n''. Во-вторых, для каждого целого числа ''i'' между <tt>1</tt> и ''n'' сгенерируем список пар от ''(i, 1)'' до ''(i, i - 1)''. Это можно сделать при помощи комбинации <tt>range</tt> и <tt>map</tt>:
<font size=3><syntaxhighlight lang=Scala>
List.range(1, i) map (x => (i, x))
</syntaxhighlight></font>
Наконец, скомбинируем все подсписки при помощи <tt>foldRight</tt> с <tt>:::</tt>. Объединение всего сказанного дает следующее выражение:
<font size=3><syntaxhighlight lang=Scala>
List.range(1, n)
.map(i => List.range(1, i).map(x => (i, x)))
.foldRight(List[(Int, Int)]()) {(xs, ys) => xs ::: ys}
.filter(pair => isPrime(pair._1 + pair._2))
</syntaxhighlight></font>
<font size=3>'''Сглаживающие преобразования'''</font>
Комбинация преобразования и затем конкатенации подсписков результатов преобразования — настолько частая операция, что для этого есть специальный метод в классе <tt>List</tt>:
<font size=3><syntaxhighlight lang=Scala>
abstract class List[+A] { …
def flatMap[B](f: A => List[B]): List[B] = this match {
case Nil => Nil
case x :: xs => f(x) ::: (xs flatMap f)
}
}
</syntaxhighlight></font>
При помощи <tt>flatMap</tt> выражение для пар, чья сумма — простое число, можно записать более кратко:
<font size=3><syntaxhighlight lang=Scala>
List.range(1, n)
.flatMap(i => List.range(1, i).map(x => (i, x)))
.filter(pair => isPrime(pair._1 + pair._2))
</syntaxhighlight></font>
== Заключение ==
| |||