Haskell中的定点组合子

Question

根据定义,定点组合器并不总能产生正确的答案:

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个参数的句柄功能)不被使用？

Answer 1

定点组合器找到函数的最小定义的固定点,在您的情况下为⊥(非终止确实是未定义的值).

您可以检查,在您的情况下

(\x -> x * x) ? = ?

即?确实是固定点\x -> x * x.

至于为什么fix定义那样:主要的fix是允许你使用匿名递归,为此你不需要更复杂的定义.

Answer 2

您的示例甚至没有进行类型检查:

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

这毫无意义.

Answer 3

我并不完全有资格谈论“定点组合器”是什么，或者“最小定点”是什么，但是可以使用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传入函数的不动点。它反复调用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已经存在了吗？停止... 胡闹时间！

兜兜转转(a -> a) -> (a -> Bool) -> a -> a，第一个打击是until。

until p f产生应用f直到p保持的结果。

那么你有它。事实证明，myFix = flip until.