Haskell中的递归lambda

Question

让我们看看使用lambda函数分析Haskell中的factorial代码:

y f x = f (y f) x

factorial = y (\t n -> if n == 1 then 1 else n * t(n-1))

我无法理解它是如何工作的.我知道它与lambda演算有关,但是现在我对它并不熟悉,所以我必须在没有它或知识最少的情况下理解.我的疑问是:阶乘的定义是什么？我的意思是这个f:y f x = f(yf)x.

那么这里有什么？y(\ tn - >如果n == 1那么1其他n*t(n-1))

请解释一下,也许扩展递归？

Answer 1

在f中factorial是(\t n -> if n == 1 ...) 拉姆达

y是一个所谓的定点组合器,它用于在lambda-calculus中启用递归定义(它f一次又一次地递归地应用于它的参数)

要了解它的工作原理,您可以手动进行一些评估:

factorial 3
= y (\t n -> ...) 3
{ def y and y (\t n -> ...) = factorial by eta-red. }
= (\t n -> ...) factorial 3
{ t = factorial, n = 3 -> else case }
= 3 * factorial 2
= 3 * (y (\t n -> ...) 2)
= 3 * ((\t n -> ...) factorial 2)
= { t = factorial, n = 2 -> else case }
= 3 * (2 * factorial 1)
= 3 * (2 * (y (\t n -> ...) 1))
= 3 * (2 * ((\t n -> ...) factorial 1)))
{ t = factorial n = 1 -> then case }
= 3 * (2 * 1)
= 6