不動点コンビネータは、定義が与えられた場合、常に正しい答えを生成するとは限りません。
fix f = f (fix f)
次のコードは終了しません。
fix (\x->x*x) 0
もちろん、fix常に正しい答えが出せるとは限りませんが、これを改善できないかと考えていました。
確かに上記の例では、次のような修正を実装できます。
fix f x | f x == f (f x) = f x
| otherwise = fix f (f x)
正しい出力が得られます。
上記の定義 (または、この 1 つのハンドル関数は 1 つのパラメーターしかないため、さらに優れたもの) が代わりに使用されない理由は何ですか?
あなたの例は型チェックさえしません:
Prelude> fix (\x->x*x) 0
<interactive>:1:11:
No instance for (Num (a0 -> t0))
arising from a use of `*'
Possible fix: add an instance declaration for (Num (a0 -> t0))
In the expression: x * x
In the first argument of `fix', namely `(\ x -> x * x)'
In the expression: fix (\ x -> x * x) 0
そして、それが期待どおりに機能しない理由の手がかりを与えてくれます。無名関数のxは、数値ではなく関数であると想定されています。この理由は、Vitus が示唆するように、修正点コンビネータは、実際に再帰を記述せずに再帰を記述する方法だからです。一般的な考え方は、次のような再帰的な定義
f x = if x == 0 then 1 else x * f (x-1)
次のように書くことができます
f = fix (\f' x -> if x == 0 then 1 else x * f' (x-1))
あなたの例
fix (\x->x*x) 0
したがって、式に対応します
let x = x*x in x 0
これは意味がありません。
「固定点コンビネータ」や「最小不動点」とは何かについて話す資格はまったくありませんが、特定の関数を近似fixするために-esque 手法を使用することは可能です。
Scala by Exampleセクション 4.4 を Haskell に翻訳する:
sqrt' :: Double -> Double
sqrt' x = sqrtIter 1.0
where sqrtIter guess | isGoodEnough guess = guess
| otherwise = sqrtIter (improve guess)
improve guess = (guess + x / guess) / 2
isGoodEnough guess = abs (guess * guess - x) < 0.001
この関数は、推測が「十分」であると判断するまで、推測を繰り返し「改善」することによって機能します。このパターンは次のように抽象化できます。
myFix :: (a -> a) -- "improve" the guess
-> (a -> Bool) -- determine if a guess is "good enough"
-> a -- starting guess
-> a
fixApprox improve isGoodEnough startGuess = iter startGuess
where iter guess | isGoodEnough guess = guess
| otherwise = iter (improve guess)
sqrt'' :: Double -> Double
sqrt'' x = myFix improve isGoodEnough 1.0
where improve guess = (guess + x / guess) / 2
isGoodEnough guess = abs (guess * guess - x) < 0.001
Scala by Example セクション 5.3 も参照してください。渡されfixApproxた関数の固定小数点を近似するために使用できます。出力まで、入力に対して improve繰り返し呼び出します。improveisGoodEnough
実際、myFix近似だけでなく、正確な答えにも使用できます。
primeAfter :: Int -> Int
primeAfter n = myFix improve isPrime (succ n)
where improve = succ
isPrime x = null [z | z <- [2..pred x], x `rem` z == 0]
これは素数を生成するかなりばかげた方法ですが、要点を示しています。うーん…今思うと…なんかもうあるのかなmyFix？やめて…フーグルタイム！
Hoogling(a -> a) -> (a -> Bool) -> a -> a、最初のヒットはuntil.
until p ff保持するまで適用した結果が得られpます。
さて、あなたはそれを持っています。結局のところ、myFix = flip until.
あなたはおそらく意味しましたiterate：
*Main> take 8 $ iterate (^2) (0.0 ::Float)
[0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0]
*Main> take 8 $ iterate (^2) (0.001 ::Float)
[1.0e-3,1.0000001e-6,1.0000002e-12,1.0000004e-24,0.0,0.0,0.0,0.0]
*Main> take 8 $ iterate (^2) (0.999 ::Float)
[0.999,0.99800104,0.9960061,0.9920281,0.9841198,0.96849173,0.93797624,0.8797994]
*Main> take 8 $ iterate (^2) (1.0 ::Float)
[1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0]
*Main> take 8 $ iterate (^2) (1.001 ::Float)
[1.001,1.002001,1.0040061,1.0080284,1.0161213,1.0325024,1.0660613,1.1364866]
ここに、分析に明示的に使用できるすべての実行履歴があります。で固定小数点の検出を試みることができます
fixed f from = snd . head
. until ((< 1e-16).abs.uncurry (-).head) tail
$ _S zip tail history
where history = iterate f from
_S f g x = f x (g x)
その後
*Main> fixed (^2) (0.999 :: Float)
0.0
ただし、試行fixed (^2) (1.001 :: Float)すると無限にループするため、収束のために個別のテストを開発する必要があります。その場合でも、1.0などの忌避性の固定小数点の検出にはさらに詳細な調査が必要になります。
比較できない可能性があるためfix、言及した方法を定義することはできません。f xたとえば、次の例を考えてみましょう。
myFix f x | f x == f (f x) = f x
| otherwise = myFix f (f x)
addG f a b =
if a == 0 then
b
else
f (a - 1) (b + 1)
add = fix addG -- Works as expected.
-- addM = myFix addG (Compile error)