haskell : how to get fix point of a function?

Question

函数 f 的不动点是满足 f(x)=x 的值 x 。编写一个函数fix，它接受函数f并返回其固定点。

例如:伪代码如下:

f(x)= 
if (x=f(x)) return x
      else return f(f(x))

如何使用 Haskell 编写它？

Answer 1

从应用的角度来看，不动点有很多种。例如，我想区分逻辑固定点和分析固定点。该线程中的大多数答案都讨论了逻辑修复点。它可以用 Haskell 写得非常漂亮，如下

fix :: (a -> a) -> a
fix f = x where x = f x

甚至

fix :: (a -> a) -> a
fix f = f (fix f)

这种逻辑修复最终成为讨论递归并将其引入语言的某种自然方式。

分析修复经常出现在数值计算中，并且具有一些不同但相关的含义。我们将从类型开始。

fixa :: (a -> a -> Bool) -> (a -> a) -> a -> Int -> a

这显然比简单的修复更复杂，因为它代表了 protected 下降。让我们开始编写 fixa 来为这些参数命名

fixa ok iter z n

目标是重复将 iter 应用于起始点 z，直到 n(正整数)达到 0 或 ok current previous 为 True。该实现读起来几乎与此处的散文完全相同。

fixa ok iter z 0 = z
fixa ok iter z n = loop z n where
  loop z n = 
    let next = iter z
        in if (ok next z)
          then next
          else loop next (n-1)

像这样的函数的值(value)在于我们可以用它来执行迭代数值算法，例如牛顿法

newton :: (Double -> Double) -> (Double -> Double) -> Double -> Double
newton f f' z = fixa (\a b -> a - b < 1e-6) (\x -> x - f x / f' x) z 1000

我们还可以通过使用 Haskell 的惰性求值来显着地改进它，以输出一个惰性结果列表，而不仅仅是最后一点。当我们这样做时，我们不再需要手动循环计数器，因为由消费者决定如何管理此改进列表。

fixaList :: (a -> a -> Bool) -> (a -> a) -> a -> [a]
fixaList ok iter z = loop z where
  loop z = let next = iter z
           in if (ok next z)
             then cycle next -- we'll return next forever
             else z : loop next

fixa ok iter z n = fixaList ok iter z !! n

事实上，我们也不再需要ok测试，这也可以留给消费者

fixaList :: (a -> a) -> a -> [a]
fixaList iter z = loop z where loop z = z : loop (iter z)

fixa iter z n = take n (fixaList iter z)

现在 fixaList 开始看起来有点像 fix

fix      f      = x      where x      = f x
fixaList iter z = loop z where loop z = z : loop (iter z)

事实上，我们可以将 fixaList 视为专门的 fix 并使用 fix 来编写它

fixaList iter z = fix (\loop z -> z : loop (iter z)) z
-- or, eta reduce to
fixaList iter   = fix (\loop z -> z : loop (iter z))

这是一个很长的说法，逻辑不动点严格来说比分析不动点更强大。