不動点アルゴリズム

昨日の論文において「関数型言語は不動点計算に向かない，なぜならエンコードしなければならないから」的なことが書かれていたので，不動点アルゴリズムについて調べてみた

　これが繰り返しの４２番目のデータとして、表示される。およそ、解が出るまでに数百回の繰り返しが必要になる。
(中略）
人口単体上にあるのか基本単体上にあるのかを区別している。
(中略）
資本と労働、貿易の各超過需要と税と貯蓄に関する超過収入が計算されている

んー，なんか経済とかの計算に使うのかな？となると昨日のcpoはCost-per-orderかもしらん（msakaiさんより：Complete Partial Orderだそうです．）

反復改良法

これを用いた sqrt, fixed-point の実装：

これは，どうもニュートン法のにおいがする．たしかに点が動かなくなるまで繰り返すのがニュートン法だ．

ところで，関数型言語だとニュートン法てそんなに難しいのか？

Haskell で難なく書いている．

cbrt e x = iter 1.0 x x
  where iter old new x
           | good old new = new
           | otherwise    = iter new (improve new x) x
        improve g x  = (x / g^2 + 2 * g) / 3
        good old new = abs (1 - old / new) < e

あ，この「ループを末尾再帰とテンポラリ引数 old とか new とかで無理やり再現」が「エンコード」と主張しているのかも．