haskell - 修复的固定点 :: Eq a => (a -> a) -> a -> a

Question

大家好，我正在尝试实现高阶函数 fix，它从初始点计算任意函数的有吸引力的不动点。也就是说，对于给定的和，形式的不动点。f :: a -> axfᴷ(x)fx

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

注意：如果函数没有从起点收敛，您的函数将不会终止。有人能帮助我吗？我试过但它没有返回任何东西

score 7 · Accepted Answer

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

因此，这意味着基本上您x在where子句中构造了一个变量，而不是函数的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 == x2 = x
        | otherwise = fix f x2
    where x2 = f x

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

score 4 · Accepted Answer

为下一步的迭代取一个不同的名称，如下所示：

where x' = f x

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

score 4 · Accepted Answer

你已经有了如何fix从头开始写作的答案。如果你想尝试使用一些标准的 Haskell 函数，我建议你看看 function until。

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

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

fix = until p

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

3 回答 3