Y组合子实现 Lambda 定义一阶递归函数

前言

我们知道,在无类型的 $\lambda$ 演算中,你不能定义包含自身的函数,那么如何用 $\lambda$ 描述递归函数呢?

不动点

对于一个函数 $f$,若存在 $x$ 使得 $f(x)=x$,则称 $x$ 是函数 $f$ 的不动点。不动点并不一定只存在一个。

不动点组合子

不动点组合子是一个用于计算其他函数不动点的高阶函数。

Y组合子

$Y$ 组合子的定义是

$$Y=\lambda f. \left(\lambda x. f \left(x\ x \right) \right)\ \left(\lambda x. f \left(x\ x \right) \right)$$

易知 $Y f = f \left(Y f \right)$ 成立.

Y组合子应用

我们可以利用 $Y$ 组合子将函数自身当作参数传入函数中,通过对这个参数的应用来实现递归。比如阶乘函数:

$$Y \left(\lambda f. \lambda n. \begin{cases} 1 & n=0 \\ n \times \left(f\ n-1\right) & n \ge 1 \end{cases} \right)$$

任何一阶递归函数都可以用 $Y$ 组合子来定义.

本文《Y组合子实现 Lambda 定义一阶递归函数》由 RM Olive (rmolives@gmail.com) 发布,如有版权纠纷及其他问题可以与我取得联系进行解决。
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇