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

Содержимое удалено Содержимое добавлено
Начат перевод главы 5.
Правка перевода главы 12.
Строка 625:
 
== Анонимные функции ==
 
== Каррирование ==
 
Последняя формулировка суммирующей функции уже довольно компактна. Но мы можем еще лучше! Заметим, что <tt>a</tt> и <tt>b</tt> появляются как параметры и аргументы каждой функции, но они, похоже, не участвуют в интересных комбинациях. Можно ли от них избавиться?
 
Давайте попробуем переписать <tt>sum</tt> так, чтобы она не принимала границы интервала <tt>a</tt> и <tt>b</tt> как параметры:
 
<font size=3><syntaxhighlight lang=Scala>
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
}
</syntaxhighlight></font>
 
== Пример: поиск неподвижных точек функций ==
== Заключение ==
Строка 1089 ⟶ 1103 :
= Вычисления с потоками =
 
В предыдущих главах рассматривались переменные, присваивание и объекты, сохраняющие состояние. Мы видели, как объекты реального мира, которые изменяются со временем, могут быть смоделированы изменением состояния переменных в вычислении. Таким образом временные изменения в реальном мире моделируются временными изменениями в выполнении программы. Конечно, такие временные изменения обычно сокращаютсясокращены или растягиваютсярастянуты, но их относительный порядок остаётся неизменным. (?)Такой подход представляется вполне естественным, но за него приходится платить: наша простая и выразительная модель
Такой подход представляется вполне естественным, но за него приходится платить: наша простая и выразительная модель
подстановок для функционального вычисления будет более не применима, если мы введём переменные
и присваивание.
 
Есть ли другой способ? Можем ли мы моделировать изменение состояния в реальном мире, используя лишь функции без побочных
Есть ли другой способ? Можем ли мы моделировать изменение состояния в реальном мире, используя лишь функции без побочных эффектов? Руководствуясь математикой, определенно можно дать ответ: "да". Величина, изменяемая со временем, просто представляется функцией <tt>f(t)</tt> с параметром времени <tt>t</tt>. То же самое можно проделать с вычислениями, но вместо переписывания переменной последовательностью значений, мы представим все эти значения списком. Так что изменяемая переменная <tt>'''var''' x: T</tt> заменяется неизменяемым значением <tt>'''val''' x: List[T]</tt>. В сущности, мы поменяли память на время — теперь различные значения переменной существуют одновременно, как различные элементы списка. Преимуществом такого подхода будет возможность "путешествия по времени", т.е. просмотра нескольких последовательных значений одновременно. Другое преимущество заключается в том, что мы можем использовать мощную библиотеку функций над списками, и это часто упрощает вычисления. Например, рассмотрим императивный способ вычисления суммы всех простых чисел из некоторого
эффектов? Руководствуясь соображениями математики, можно дать ответ: "да".
Величина, изменяемая со временем просто представляется функцией f(t) с параметром времени t. И точно так же может быть
вычислена. Но вместо переписывания переменной полученными результатами мы будем собирать их в список.
Так что изменяемая переменная var x: T заменяется неизменяемым значением val x: List[T].
В сущности, теперь различные значения переменной существуют одновременно, как различные элементы списка.
Преимуществом такого подхода будет возможность "путешествия по времени", т.е. просмотра нескольких последовательных
значений одновременно. Другое преимущество заключается в том, что мы можем использовать библиотеку функций над списками,
и это часто упрощает вычисления. Например, рассмотрим императивный способ вычисления суммы всех простых чисел из некоторого
интервала:
 
<font size=3><syntaxhighlight lang=Scala>
def sumPrimes(start: int, end: int): int = {
def sumPrimes(start: int, end: int): int = {
var i = start
var acci = 0start
var acc = 0
while (i < end) {
if (isPrime(i)) acc = acc + i
i = i + 1
}
acc
}
acc
}
</syntaxhighlight></font>
 
Заметьте, переменная <tt>i</tt> "пробегает" все значения из интервала <tt>[start .. end1end-1]</tt>.
Более функциональный способ заключается в представлении списка значений i явно, как range(start, end).
Далее функция может быть переписана так:
 
Более функциональный способ заключается в представлении списка значений <tt>i</tt> явно, как <tt>range(start, end).</tt> Тогда функция может быть переписана так:
def sumPrimes(start: int, end: int) =
sum(range(start, end) filter isPrime)
Бесспорно, вторая программа короче и яснее! Однако, функциональная программа также и менее эффективна, поскольку она
конструирует список список чисел из интервала а затем ещё один для простых чисел.
Ещё хуже с точки зрения эффективности следующий пример. Требуется найти второе простое число между 1000 и 10000:
 
<font size=3><syntaxhighlight lang=Scala>
range(1000, 10000) filter isPrime at 1
def sumPrimes(start: int, end: int) =
Здесь конструируется список всех чисел между 1000 and 10000. Но большая часть этого списка не будет использована!
sum(range(start, end) filter isPrime)
Мы можем достичь эффективного выполнения для случаев, таких как этот, с помощью уловки:
</syntaxhighlight></font>
Избегайте вычисления хвоста последовательности до тех пор, пока он действительно не понадобится.
Определим новый класс Stream (Поток) для таких последовательностей.
Потоки создаются с помощью empty - константы и конструктора cons, они определены в модуле scala.Stream.
Например, следующее выражение создаёт поток с элементами 1 и 2:
 
Бесспорно, вторая программа короче и яснее! Однако функциональная программа также и менее эффективна, поскольку она конструирует список список чисел из интервала а затем ещё один для простых чисел.
Stream.cons(1, Stream.cons(2, Stream.empty))
Ещё хуже с точки зрения эффективности следующий пример.
В качестве другого примера, вот аналог List.range:
 
Требуется найти второе простое число между 1000 и 10000:
def range(start: int, end: int): Stream[int] =
 
if (start >= end) Stream.empty
<font size=3><syntaxhighlight lang=Scala>
else Stream.cons(start, range(start + 1, end))
range(1000, 10000) filter isPrime at 1
Даже хотя Stream.range и List.range выглядят похоже, их поведение во время выполнения совершенно различно:
</syntaxhighlight></font>
Stream.range немедленно возвращает объект Stream первый элемент которого - start.
 
Все другие элементы вычисляются только если они требуются (вызов метода tail).
Здесь конструируется список всех чисел между 1000 and 10000. Но большая часть этого списка не будет использована! Но мы можем достичь эффективного выполнения для аналогичных случаев с помощью уловки:''избегайте вычисления хвоста последовательности до тех пор, пока он действительно не понадобится.''
Как для списков для потоков определены isEmpty, head и tail.
 
Распечатать все элементы списка можно так:
Определим новый класс <tt>Stream</tt> (поток) для таких последовательностей. Потоки создаются с помощью константы <tt>empty</tt> и конструктора <tt>cons</tt>, которые определены в модуле <tt>scala.Stream</tt>. Например, следующее выражение создаёт поток с элементами <tt>1</tt> и <tt>2</tt>:
 
def print(xs: Stream[a]) {
<font size=3><syntaxhighlight lang=Scala>
if (!xs.isEmpty) { System.out.println(xs.head); print(xs.tail) }
Stream.cons(1, Stream.cons(2, Stream.empty))
}
</syntaxhighlight></font>
Потоки также поддерживают другие аналоги методов на списках. Например, мы можем найти второе простое число между
 
1000 и 10000 с помощью методов filter и apply:
Вот другой пример, аналог <tt>List.range</tt>, возвращающий поток вместо списка:
 
Stream.range(1000, 10000) filter isPrime at 1
<font size=3><syntaxhighlight lang=Scala>
Различие от предыдущей реализации на списках в том что теперь нет необходимости конструировать и проверять на простоту
def range(start: int, end: int): Stream[int] =
другие числа, после третьего. Два метода из класса List, не поддерживаемые классом Stream это :: и :::.
if (start >= end) Stream.empty
Причина в том, что эти методы требуют передачи правых аргументов, а это означает, что аргументы должны быть вычислены
else Stream.cons(start, range(start + 1, end))
до вызова метода. Например, в случае x :: xs на списках, хвост xs должен быть вычислен
</syntaxhighlight></font>
до оператора :: . Это не работает для потоков, поскольку хвост потока пока не потребуется в вычислениях,
 
не должен вычисляться. Объяснение почему метод ::: не адаптируется для потоков - аналогично.
(Эта функция, как и предыдущая, тоже определена в модуле <tt>Stream</tt>). Даже хотя <tt>Stream.range</tt> и <tt>List.range</tt> выглядят похоже, их поведение во время выполнения совершенно разное:
Вместо x :: xs, используют Stream.cons(x, xs). Вместо xs ::: ys, - xs append ys.
 
<tt>Stream.range</tt> немедленно возвращает объект <tt>Stream</tt>, первый элемент которого — <tt>start</tt>. Все другие элементы вычисляются, только если они ''потребуются'' при помощи вызова метода <tt>tail</tt> (который может никогда не произойти).
 
Доступ к потокам — такой же, как к спискам. Как и для списков, для потоков определены базовые методы доступа <tt>isEmpty</tt>, <tt>head</tt> и <tt>tail</tt>. Например, распечатать все элементы потока можно так:
 
<font size=3><syntaxhighlight lang=Scala>
def print(xs: Stream[a]) {
if (!xs.isEmpty) { System.out.println(xs.head); print(xs.tail) }
}
</syntaxhighlight></font>
 
Потоки также поддерживают почти все другие методы, определенные для списков (см. ниже, в чем множества их методов различаются). Например, мы можем найти второе простое число между <tt>1000</tt> и <tt>10000</tt> с помощью методов <tt>filter</tt> и <tt>apply</tt> на интервальном потоке:
 
<font size=3><syntaxhighlight lang=Scala>
Stream.range(1000, 10000) filter isPrime at 1
</syntaxhighlight></font>
 
Различие с предыдущей списковой реализацей в том, что теперь нет необходимости конструировать и проверять на простоту числа после <tt>1013</tt>.
 
'''Склеивание потоков.''' Два метода из класса <tt>List</tt>, не поддерживаемые классом <tt>Stream</tt> это <tt>::</tt> и <tt>:::</tt>. Причина в том, что эти методы раскрываются с правых аргументов, а это означает, что эти аргументы должны быть вычислены до вызова метода. Например, в случае <tt>x :: xs</tt> на списках, хвост <tt>xs</tt> должен быть вычислен до вызова оператора <tt>::</tt> и конструирования нового списка. Это не работает для потоков, поскольку хвост потока не должен вычисляться, пока не потребуется операции <tt>tail</tt>. Объяснение, почему метод <tt>:::</tt> не адаптируется для потоков — аналогично.
 
Вместо <tt>x :: xs</tt> для создания потока с первым элементом <tt>x</tt> и (невычисленным) остатком <tt>xs</tt> используют <tt>Stream.cons(x, xs)</tt>. Вместо <tt>xs ::: ys</tt> используют операцию <tt>xs append ys</tt>.
 
= Итераторы =