haskell - 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

Answer 2

Your example does not even typecheck:

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

And that gives the clue as to why it doesn't work as you expect. The x in your anonymous function is supposed to be a function, not a number. The reason for this is, as Vitus suggests, that a fixpoint combinator is a way to write recursion without actually writing recursion. The general idea is that a recursive definition like

f x = if x == 0 then 1 else x * f (x-1)

can be written as

f    = fix (\f' x -> if x == 0  then 1 else x * f' (x-1))

Your example

fix (\x->x*x) 0

thus corresponds to the expression

let x = x*x in x 0

which makes no sense.

Answer 3

I'm not entirely qualified to talk about what the "fixpoint combinator" is, or what the "least fixed point" is, but it is possible to use a fix-esque technique to approximate certain functions.

Translating Scala by Example section 4.4 to 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

This function works by repeatedly "improving" a guess until we determine that it is "good enough". This pattern can be abstracted:

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

See also Scala by Example section 5.3. fixApprox can be used to approximate the fixed point of the improve function passed into it. It repeatedly invokes improve on the input until the output isGoodEnough.

In fact, you can use myFix not only for approximations, but for exact answers as well.

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]

This is a pretty dumb way to generate primes, but it illustrates the point. Hm...now I wonder...does something like myFix already exist? Stop...Hoogle time!

Hoogling (a -> a) -> (a -> Bool) -> a -> a, the very first hit is until.

until p f yields the result of applying f until p holds.

Well there you have it. As it turns out, myFix = flip until.

Answer 4

You probably meant 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]

Here you have all the execution history explicitly available for your analysis. You can attempt to detect the fixed point with

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)

and then

*Main> fixed (^2) (0.999 :: Float)
0.0

but trying fixed (^2) (1.001 :: Float) will loop indefinitely, so you'd need to develop separate testing for convergence, and even then detection of repellent fixed points like 1.0 will need more elaborate investigation.

Answer 5

You can't define fix the way you've mentioned since f x may not even be comparable. For instance, consider the example below:

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)