Scala в примерах: различия между версиями
Содержимое удалено Содержимое добавлено
Annayudi (обсуждение | вклад) →Каррирование: — закончен перевод параграфа |
Annayudi (обсуждение | вклад) →Пример: поиск неподвижных точек функций: — перевод параграфа |
||
Строка 785:
== Пример: поиск неподвижных точек функций ==
Число <tt>x</tt> называется ''неподвижной точкой'' функции <tt>f</tt>, если <tt>f(x) = x</tt>.
Для некоторых функций <tt>f</tt> можно найти неподвижную точку, стартовав с начальной догадки и затем применяя <tt>f</tt> раз за разом, пока значение не перестанет изменяться (или изменения будут не больше некоторого значения). Это возможно, если последовательность <tt>x, f(x), f(f(x)), f(f(f(x))), …</tt> сходится к неподвижной точке <tt>f</tt>. Эта идея выражена в следующей фунции поиска неподвижной точки:
<font size=3><syntaxhighlight lang=Scala>
val tolerance = 0.0001
def isCloseEnough(x: Double, y: Double) = abs((x - y) / x) < tolerance
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)
}
</syntaxhighlight></font>
Теперь применим эту идею при формулировании функции вычисления квадратных корней. Начнем со спецификации <tt>sqrt</tt>: <tt> sqrt(x) = the ''y'' such that y * y = x = the ''y'' such that y = x / y</tt>.
Заметьте, что <tt>sqrt(x)</tt> — неподвижная точка функции <tt>y => x / y</tt>. Поэтому <tt>sqrt(x)</tt> можно вычислить при помощи итерации неподвижной точки:
<font size=3><syntaxhighlight lang=Scala>
def sqrt(x: double) = fixedPoint(y => x / y)(1.0)
</syntaxhighlight></font>
Но если мы сделаем так, мы обнаружим, что вычисления не сходятся. Давайте добавим в функцию выражение печати значения <tt>quess</tt>:
<font size=3><syntaxhighlight lang=Scala>
def fixedPoint(f: Double => Double)(firstGuess: Double) = {
def iterate(guess: Double): Double = {
val next = f(guess)
println(next)
if (isCloseEnough(guess, next)) next
else iterate(next)
}
iterate(firstGuess)
}
</syntaxhighlight></font>
Тогда <tt>sqrt(2)</tt> выведет
<pre>
2.0
1.0
2.0
1.0
2.0
…
</pre>
Такие колебания можно контролировать, не давая значению догадки так сильно изменяться. Это можно сделать ''усреднением'' значений:
<font size=3><syntaxhighlight lang=Bash>
scala> def sqrt(x: Double) = fixedPoint(y => (y + x/y) / 2)(1.0)
sqrt: (Double)Double
scala> sqrt(2.0)
1.5
1.4166666666666665
1.4142156862745097
1.4142135623746899
1.4142135623746899
</syntaxhighlight></font>
На самом деле, расширение функции <tt>fixedPoint</tt> дает в точности определение неподвижной точки из Параграфа 4.4.
Предыдущий пример показал, что выразительная мощность языка значительно увеличивается, если функции можно передавать как аргументы. Следующий пример показывает, что функции, возвращающие функции, тоже могут быть полезны.
Рассмотрим опять итерации неподвижной точки. Мы начали с наблюдения, что <math>\sqrt{(x)}</math> это неподвижная точка функции <tt>y => x / y</tt>. Затем мы свели итерации к неподвижной точке, усредняя последовательные значения. Техника ''торможения усреднением'' настолько часто применяется, что на может быть вынесена в отдельную фунцию:
<font size=3><syntaxhighlight lang=Scala>
def averageDamp(f: Double => Double)(x: Double) = (x + f(x)) / 2
</syntaxhighlight></font>
При помощи <tt>averageDamp</tt> мы можем переформулировать функцию вычисления квадратного корня так:
<font size=3><syntaxhighlight lang=Scala>
def sqrt(x: Double) = fixedPoint(averageDamp(y => x/y))(1.0)
</syntaxhighlight></font>
Это выражает элементы алгоритма максимально ясно.
'''Упражнение 5.3.1''' Напишите функцию для вычисления кубических корней, используя <tt>fixedPoint</tt> и <tt>averageDamp</tt>.
== Заключение ==
== Использованные элементы языка ==
| |||