Haskell "fix" 关键字在声明递归 lambda 函数时失败

Question

似乎一个函数应该有一个递归的名字（以便调用自己），那么lambda函数是如何递归的？

我搜索了维基百科，它说这可以由 "Y-combinator" 完成。我没有太多的数学理论背景，它只是告诉我 "Y-combinator" 是由 Haskell 自己发现的。在Haskell语言中调用"fix"关键字，我试过：

Prelude> let fact = fix (\f n -> if n == 0 then 1 else n * (f (n-1)))

<interactive>:17:12: Not in scope: ‘fix’

似乎失败了，但是如何使用 "fix" 关键字来达到我预期的效果？

Answer 1

fix不是关键字，是Data.Function模块中定义的函数。因此，要使用它，您必须导入该模块。

import Data.Function

或在 GHCi 中：

:m Data.Function

Answer 2

fix 定义为：

fix :: (a -> a) -> a
fix f = let x = f x in x

因此它扩展为 f (f (f (f ...))) 即输入函数 f 对某些参数 x.

的无限嵌套应用序列

您可以给您的 lambda 函数一个顶级定义，例如

factF f n = if n == 0 then 1 else n * f (n - 1)

或等同于：

factF :: (Int -> Int) -> (Int -> Int)
factF f = \n -> if n == 0 then 1 else n * f (n - 1)

你可以把这个函数提供给fix得到一个函数(Int -> Int)即

fact :: (Int -> Int)
fact = fix factF

如果你展开这个定义你会得到

factF (factF (factF (factF ...)))
=> \n -> if n == 0 then 1 else (factF (factF (factF ...)))

由于懒惰，factF 的重复应用仅在 n /= 0 时才被评估，因此应用于 0 的上述函数将立即评估为 1。

您可以在这个扩展中看到 factF 作为参数提供给它自己，然后它应用于较小版本的 n。由于 factN 与您的 lambda 函数相同，因此那里发生了同样的事情 - lambda 内部的参数 f 是 lambda 本身，然后可以递归调用它。