使用 fix 计算斐波那契数列

Question

我正在尝试使用函数 fix :: (a -> a) -> a.

了解这个阶乘示例的工作原理

factabs :: (Num a, Eq a) => (a -> a) -> a -> a
factabs fact 0 = 1
factabs fact x = x * fact (x-1)

f :: (Num a, Eq a) => a -> a
f = fix factabs

我不明白为什么 fix factabs 有这种类型...fix 需要类型 a -> a 的函数，我们如何将它应用到类型 [=16] 的函数=]（一个有两个参数的函数）？我完全糊涂了...

基本上我是想弄清楚如何将下面的函数 limit 转换为使用 fix 的函数。非常感谢任何帮助。

limit f n
    | n == next       = n
    | otherwise       = limit f next
    where
      next = f n

Answer 1

fix expects a function of type a -> a, how can we apply it to a function of type (a -> a) -> a -> a (a function that takes two parameters)? I am totally confused...

之所以可行，是因为所有Haskell 函数只接受一个参数。尽管我们经常想到这种类型...

(a -> a) -> a -> a

...作为两个参数的函数之一，我们也可以读成...

(a -> a) -> (a -> a)

... 也就是说，接受一个参数（a -> a 函数）并生成一个参数（a 类型）的函数之一。现在如果我们采取...

fix :: (b -> b) -> b

...我们可以通过将 b 替换为 (a -> a).

来查看 factabs 如何适合它

Basically I was trying to figure out how to convert the function limit below to something that uses fix.

你需要做的就是，从原始定义开始，用额外的参数替换 limit 的任何递归调用，并将这个 limit-with-an-extra-argument 传递给 fix（如您所见，类型将立即匹配）。

Answer 2

仅作记录，这是我在问题中发布的 limit 函数的一个版本，它使用 fix:

limit :: Eq a => (a -> a) -> a -> a
limit = fix (\g f x -> let x' = f x
                       in if x == x' then x else g f x')

使用 fix 计算斐波那契数列

Calculating fibonnacci numbers using fix

haskell

fixpoint-combinators