haskell - Calculating fibonnacci numbers using fix

Question

I am trying to understand how this factorial example works using the function fix :: (a -> a) -> a.

Example:

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

I do not see why fix factabs has this type... 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...

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

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

Answer 1

fix 需要一个类型的函数，a -> a我们如何将它应用于类型(a -> a) -> a -> a的函数（一个接受两个参数的函数）？我完全糊涂了……

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

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

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

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

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

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

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

基本上我试图弄清楚如何将limit下面的函数转换为使用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')