haskell - 如何在 Haskell 中编写递归 lambda 表达式？

Question

我不确定这是否是一种好的编程习惯，但我想知道是否可以使用 lambda 表达式定义递归函数。

这是我编的一个人为的例子:所以可以递归地定义Haskell中的阶乘函数如下

factorial :: Integer -> Integer 
factorial 1 = 1
factorial (n + 1) = (n + 1) * factorial n

现在，我想要一个函数 f这样f n = (factorial n) + 1 .而不是使用 factorial n 的名称(即事先定义)，我想定义 f在哪里 factorial n在 f 的定义中给出了一个 lambda 表达式.我可以在 f 中使用递归 lambda 定义吗？代替使用名称阶乘？

Answer 1

使用纯 lambda 表达式进行递归的规范方法是使用定点组合器，它是具有属性的函数

fixpoint f x = f (fixpoint f) x

如果我们假设存在这样的组合子，我们可以将递归函数写成

factorial = fixpoint (\ff n -> if n == 1 then 1 else n * ff(n-1))

唯一的问题是 fixpoint本身仍然是递归的。在纯 lambda 演算中，有一些方法可以创建仅由 lambda 组成的定点组合器，例如经典的“Y 组合器”:

fixpoint f = (\x -> f (x x)) (\x -> f (x x))

但是我们仍然有问题，因为根据 Haskell，这个定义不是类型良好的——而且可以证明，仅使用 lambda 和函数应用程序是无法编写类型良好的定​​点组合器的。它可以通过使用辅助数据类型来完成某种类型的递归:

data Paradox a = Self (Paradox a -> a)
fixpoint f = let half (Self twin) = f (twin (Self twin))
             in half (Self half)

(请注意，如果删除了单例数据类型的注入(inject)和投影，这正是 Y 组合子!)