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

Question

大家好我正在尝试实现高阶函数修复,它从初始点计算任意函数的有吸引力的固定f :: a -> a点x.也就是说,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

注意:如果函数没有从起点收敛,则函数不会终止.有谁可以帮助我吗 ？我试过但它没有返回任何东西

Answer 1

一个常见的误解是,当您编写时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,所以我们以先进的一步" 任务为固定点 ".