「Example5.3」の編集履歴（バックアップ）一覧はこちら
Example5.3 - (2010/10/22 (金) 13:17:20) の最新版との変更点
追加された行は緑色になります。
削除された行は赤色になります。
#co(){
5.3 Example: Finding Fixed Points of Functions
A number x is called a fixed point of a function f if
}
** 5.3 例 : 関数の不動点探索
数 x は次の条件を満たす時に、関数 f の&bold(){不動点}と呼ばれます。
f(x) = x .
#co(){
For some functions f we can locate the fixed point by beginning with an initial guess and then applying f repeatedly, until the value does not change anymore (or the change is within a small tolerance). This is possible if the sequence
}
いくつかの関数 f では、初期推定値から始めて、値が変化しなくなる (あるいは変化が小さな許容量以下になる) まで f を繰り返し適用することで不動点を求めることができます。それは、数列
x, f(x), f(f(x)), f(f(f(x))), ...
#co(){
converges to fixed point of f . This idea is captured in the following "fixed-point finding function":
}
が、f の不動点に収束すれば可能です。このアイデアを取り入れたのが次の「不動点を求める関数」です。
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)
}
#co(){
We now apply this idea in a reformulation of the square root function. Let's start with a specification of sqrt:
}
このアイデアを平方根を求める関数の再設計に応用します。sqrt の仕様から始めましょう。
#co(){
sqrt(x) = the y such that y * y = x
= the y such that y = x / y
}
sqrt(x) = y ただし y * y = x
= y ただし y = x / y
#co(){
Hence, sqrt(x) is a fixed point of the function y => x / y. This suggests that sqrt(x) can be computed by fixed point iteration:
def sqrt(x: double) = fixedPoint(y => x / y)(1.0)
But if we try this, we find that the computation does not converge. Let's instrument the fixed point function with a print statement which keeps track of the current guess value:
}
したがって sqrt(x) は関数 y=> x / y の不動点です。このことは sqrt(x) は不動点の反復で計算できることを示しています。
def sqrt(x: double) = fixedPoint(y => x / y)(1.0)
しかし実際にやってみると、計算は収束しないことが分かります。現在の推定値を追跡する print 文付きの不動点関数を実装してみます。
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)
}
#co(){
Then, sqrt(2) yields:
}
すると sqrt(2) は次のようになります。
2.0
1.0
2.0
1.0
2.0
...
#co(){
One way to control such oscillations is to prevent the guess from changing too much. This can be achieved by averaging successive values of the original sequence:
}
このような振動を抑える一つの方法は、推定値の急激な変化を防ぐことです。これは元の数列上で、続く値を&bold(){平均}すれば可能です。
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
#co(){
In fact, expanding the fixedPoint function yields exactly our previous definition of fixed point from Section 4.4.
The previous examples showed that the expressive power of a language is considerably enhanced if functions can be passed as arguments. The next example shows that functions which return functions can also be very useful.
Consider again fixed point iterations. We started with the observation that √(x ) is a fixed point of the function y => x / y. Then we made the iteration converge by averaging successive values. This technique of average damping is so general that it can be wrapped in another function.
}
実際、fixedPoint 関数を展開すると、前に 4.4 節で定義した不動点の定義と全く同じになります。
前の例では、もし関数を引数として渡すことができれば、言語の表現力が大幅に強化される、ということを示しました。次の例では、関数を返す関数もたいへん有用であることを示します。
不動点の繰り返しをもう一度考えてみましょう。√(x) が関数 y => x / y の不動点であることから始めました。次いで、続く値を平均することで繰り返しを収束させました。この&bold(){平均による減衰}というテクニックは一般的ですから、別の関数で包むことにします。
def averageDamp(f: Double => Double)(x: Double) = (x + f(x)) / 2
#co(){
Using averageDamp, we can reformulate the square root function as follows.
def sqrt(x: Double) = fixedPoint(averageDamp(y => x/y))(1.0)
This expresses the elements of the algorithm as clearly as possible.
Exercise 5.3.1 Write a function for cube roots using fixedPoint and averageDamp.
}
averageDump を使って、平方根関数を次のように再設計できます。
def sqrt(x: Double) = fixedPoint(averageDamp(y => x/y))(1.0)
Exercise 5.3.1 Write a function for cube roots using fixedPoint and averageDamp.
}
これはアルゴリズムの要素を可能な限り明確に表現しています。
&b(){演習 5.3.1 } fixedPoint と averageDump を使って、立方根を求める関数を書きなさい。
#center(){[[前ページ>Example5.2]] [[ 5 章>ExampleChap5]] [[目次>ScalaByExample和訳]] [[次ページ>Example5.4]]}
----
#comment
#co(){
5.3 Example: Finding Fixed Points of Functions
A number x is called a fixed point of a function f if
}
#setmenu2(ex-r-menu)
** 5.3 例 : 関数の不動点探索
数 x は次の条件を満たす時に、関数 f の&bold(){不動点}と呼ばれます。
f(x) = x .
#co(){
For some functions f we can locate the fixed point by beginning with an initial guess and then applying f repeatedly, until the value does not change anymore (or the change is within a small tolerance). This is possible if the sequence
}
いくつかの関数 f では、初期推定値から始めて、値が変化しなくなる (あるいは変化が小さな許容量以下になる) まで f を繰り返し適用することで不動点を求めることができます。それは、数列
x, f(x), f(f(x)), f(f(f(x))), ...
#co(){
converges to fixed point of f . This idea is captured in the following "fixed-point finding function":
}
が、f の不動点に収束すれば可能です。このアイデアを取り入れたのが次の「不動点を求める関数」です。
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)
}
#co(){
We now apply this idea in a reformulation of the square root function. Let's start with a specification of sqrt:
}
このアイデアを平方根を求める関数の再設計に応用します。sqrt の仕様から始めましょう。
#co(){
sqrt(x) = the y such that y * y = x
= the y such that y = x / y
}
sqrt(x) = y ただし y * y = x
= y ただし y = x / y
#co(){
Hence, sqrt(x) is a fixed point of the function y => x / y. This suggests that sqrt(x) can be computed by fixed point iteration:
def sqrt(x: double) = fixedPoint(y => x / y)(1.0)
But if we try this, we find that the computation does not converge. Let's instrument the fixed point function with a print statement which keeps track of the current guess value:
}
したがって sqrt(x) は関数 y=> x / y の不動点です。このことは sqrt(x) は不動点の反復で計算できることを示しています。
def sqrt(x: double) = fixedPoint(y => x / y)(1.0)
しかし実際にやってみると、計算は収束しないことが分かります。現在の推定値を追跡する print 文付きの不動点関数を実装してみます。
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)
}
#co(){
Then, sqrt(2) yields:
}
すると sqrt(2) は次のようになります。
2.0
1.0
2.0
1.0
2.0
...
#co(){
One way to control such oscillations is to prevent the guess from changing too much. This can be achieved by averaging successive values of the original sequence:
}
このような振動を抑える一つの方法は、推定値の急激な変化を防ぐことです。これは元の数列上で、続く値を&bold(){平均}すれば可能です。
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
#co(){
In fact, expanding the fixedPoint function yields exactly our previous definition of fixed point from Section 4.4.
The previous examples showed that the expressive power of a language is considerably enhanced if functions can be passed as arguments. The next example shows that functions which return functions can also be very useful.
Consider again fixed point iterations. We started with the observation that √(x ) is a fixed point of the function y => x / y. Then we made the iteration converge by averaging successive values. This technique of average damping is so general that it can be wrapped in another function.
}
実際、fixedPoint 関数を展開すると、前に 4.4 節で定義した不動点の定義と全く同じになります。
前の例では、もし関数を引数として渡すことができれば、言語の表現力が大幅に強化される、ということを示しました。次の例では、関数を返す関数もたいへん有用であることを示します。
不動点の繰り返しをもう一度考えてみましょう。√(x) が関数 y => x / y の不動点であることから始めました。次いで、続く値を平均することで繰り返しを収束させました。この&bold(){平均による減衰}というテクニックは一般的ですから、別の関数で包むことにします。
def averageDamp(f: Double => Double)(x: Double) = (x + f(x)) / 2
#co(){
Using averageDamp, we can reformulate the square root function as follows.
def sqrt(x: Double) = fixedPoint(averageDamp(y => x/y))(1.0)
This expresses the elements of the algorithm as clearly as possible.
Exercise 5.3.1 Write a function for cube roots using fixedPoint and averageDamp.
}
averageDump を使って、平方根関数を次のように再設計できます。
def sqrt(x: Double) = fixedPoint(averageDamp(y => x/y))(1.0)
Exercise 5.3.1 Write a function for cube roots using fixedPoint and averageDamp.
}
これはアルゴリズムの要素を可能な限り明確に表現しています。
&b(){演習 5.3.1 } fixedPoint と averageDump を使って、立方根を求める関数を書きなさい。
#center(){[[前ページ>Example5.2]] [[ 5 章>ExampleChap5]] [[目次>ScalaByExample和訳]] [[次ページ>Example5.4]]}
----
#comment
