如何在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给出lambda表达式的位置,而不是使用名称(即,事先定义它)f.我可以使用递归lambda定义f代替使用名称factorial吗？

Answer 1

是的,使用定点功能fix:

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

基本上,它没有名称,因为它是一个lambda表达式,所以你将函数作为参数.Fix将函数"无限地"应用于自身多次:

fix f = f (fix f)

并定义于Data.Function.

Answer 2

使用纯lambda表达式进行递归的规范方法是使用fixpoint combinator,这是一个带有属性的函数

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,这个定义并不是很好的类型 - 并且可以证明没有办法只使用lambdas和函数应用程序编写一个良好类型的fixpoint组合器.可以通过使用辅助数据类型来完成某些类型的递归:

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

(注意,如果删除了单例数据类型的注入和投影,那么这就是Y组合子!)