fix :: Eq a => (a -> a) -> a -> a 的不动点

Question

大家好，我正在尝试实现高阶函数修复，它从初始点 x 计算任意函数 f :: a -> a 的 attractive fixed point。也就是说，对于给定的 f 和 x，形式为 fᴷ(x) 的不动点。

-- CONTRACT
fix :: Eq a => (a -> a) -> a -> a
-- DEFINITION [TODO: Implement fix]
fix f x  = ?

我目前的尝试是：

fix f x | f x == x = x
        | otherwise = fix f x
    where x = f x

注意：您的如果函数不从一开始就收敛，函数将不会终止点。有人能帮助我吗？我试过了，但没有 return 任何东西

Answer 1

一个常见的误解是，当您编写 x = ... 时，您分配一个 Haskell 中的值。在 Haskell 中，一个不赋值，一个声明一个。

这意味着基本上你在 where 子句中构建了一个变量 x ，它是 而不是 头部的 x函数，所以类似于：

fix :: Eq a => (a -> a) -> a -> a
fix f _ | f x == x = x
        | otherwise = fix f x
    where x = f x

你在这里定义了 x 本身：x = f x，这意味着如果 Haskell 旨在评估它，它将开始计算 f(f(f(f(f(f(...))))))，但是没有任何检查是否已达到 固定点。

解决方法是引入一个新的变量，例如x2，这样使用：

fix :: Eq a => (a -> a) -> a -> a
fix f x | x == <b>x2</b> = x
        | otherwise = fix f <b>x2</b>
    where <b>x2</b> = f x

所以这里 x2 是下一个 x。给定x == x2，我们returnx（或x2），如果不是，我们计算f和x2的不动点，所以我们在“定点探索”中前进了一步。

Answer 2

给迭代的下一步起一个不同的名字，像这样：

where x' = f x

（而不是 where x = f x）。现在检查您现有代码的其余部分，并针对每次出现的 x 问问自己：我在这里的意思是 x 还是 x'？

Answer 3

您已经有了关于如何从头开始编写fix的答案。如果您想使用一些标准 Haskell 函数来尝试它，我建议您查看函数 until。

until :: (a -> Bool) -> (a -> a) -> a -> a

请注意 until 的类型与您想要的类型非常相似。它只需要一个 a -> Bool 形式的额外参数。表达式 until p f x 从初始点 x 开始迭代应用 f，直到满足某些条件 p。您应该可以轻松地以

的形式编写 fix

fix = until p

对于某些功能 p :: a -> Bool。现在你只需要实现这个停止条件 p，它检查你计算的点 y 是否是 f 的固定点，即如果 f y == y。

a fixed point for fix :: Eq a => (a -> a) -> a -> a