给定定义,不动点组合子并不总是产生正确的答案:
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个参数的句柄函数(?
不动点组合子找到一个函数的最小定义不动点,在你的情况下它是Ş(不终止确实是未定义的值(。
你可以检查一下,在你的情况下是
(x -> x * x) ⊥ = ⊥
即CCD_ 2实际上是CCD_。
至于为什么fix
是这样定义的:fix
的要点是允许使用匿名递归,因此不需要更复杂的定义。
您的示例甚至不进行类型检查:
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
型技术来近似某些函数。
将Scala的示例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
函数的固定点。它在输入端重复调用improve
,直到输出isGoodEnough
。
事实上,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
的东西已经存在了吗?停止Hoogle时间!
Hooling (a -> a) -> (a -> Bool) -> a -> a
,第一个命中是until
。
CCD_ 16产生应用CCD_ 17直到CCD_。
好吧,你有了。事实证明,myFix = flip until
。
您可能是指⊥
0:
*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)