J. *_*son 16
让我们假设我们有一种没有递归的语言或类似的东西.这意味着没有循环结构.这也意味着我们也有(非递归)类型,因此我们无法形成Y-combinator并逃脱.在这种语言中,我们真的很弱,与我们的许多工具分开.
但我们可以就这种语言提出一个非常好的问题.也就是说,为了使它变得像没有这种限制的语言一样强大,我们必须给它最小的东西是什么？
事实证明有两个答案.
我们可以引入递归的粘合剂,像一个let rec命令或类似Haskell的let这始终是let rec.换句话说,一种允许我们定义let x = e in b使得if在其中x是空闲的结构,e它被计算为等式上的固定点x = e.
我们可以引入该功能fix :: (a -> a) -> a,使得fix f在一个步骤减少f (fix f).
从上面的介绍中fix可以清楚地看出,可以使用递归绑定器来实现.有点不太清楚的是,递归绑定器可以使用修复从非递归绑定器实现,但我们在这里:
let x = fix $ \this -> e
该值this指的是最终绑定的整个表达式,x这正是我们想要的.
那么为什么我会不遗余力地说出以上所有内容呢？
从本质上讲,我想说,map只要您愿意fix在该列表上考虑,就不可能说通过HOF组合器实现递归.我还想争辩说,该集合中的组合器实现的任何递归都可以使用递归绑定器"显式"完成.他们同样强大.
当您考虑HOF组合器时,有趣的部分就在于foldr/ unfoldr它们自己.这些技术上比/递归粘合剂弱一些fix.优点是,如果你只使用一组选择foldr/ 类似unfoldr的原则构建一个编程语言,那么你可以获得一个非常丰富的子图灵完整语言,可以是完全或保证终止.