haskell - Haskell“修复”关键字在声明递归 lambda 函数时失败

Question

似乎一个函数应该有一个递归的名称（为了调用自己），那么 lambda 函数如何递归？

我搜索了维基百科，它说这可以通过“Y-combinator”来完成。我没有太多的数学理论背景，它只是告诉我“Y-combinator”是 Haskell 自己发现的。在 Haskell 语言中称为“修复”关键字，我尝试过：

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

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

似乎失败了，但是如何使用“修复”关键字来完成我的预期？

score 12 · Accepted Answer

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

import Data.Function

或在 GHCi 中：

:m Data.Function

score 2 · Accepted Answer

fix定义为：

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

因此它扩展为输入函数对某个参数f (f (f (f ...)))的无限嵌套应用序列。fx

您可以为您的 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 函数相同，因此在那里发生了同样的事情 - flambda 内部的参数是 lambda 本身，然后它可以递归调用。

2 回答 2