Y-Combinator实例

最近我一直在阅读关于函数式编程的一些知识，我正在努力研究Y-Combinator。 我知道你可以使用Y-Combinator来有效地实现recursion，而不是直接支持recursion的语言。 但是，我可能使用的每种语言已经支持recursion，所以我不确定使用Y-Combinator是多么有用。

Y-Combinator的用法有没有更好的实用例子？ 有没有人真的在生产代码中使用过？ 或者是使用Y-Combinator实际上只是一个弯曲的学术练习（虽然是一个很酷的）。

Answer 1

我不同意其他答案： 定点（Y）组合器确实有实际的应用 ，但需要一个非常有想象力的头脑才能find它们。 像布鲁斯麦克亚当。 以下是他的论文“关于包装 ：

用于计算固定点的Y组合器可以用标准ML表示。 它经常被用作高阶函数的例子，但通常不被认为是有用的编程结构。 在这里，我们看看基于Y组合器和包装器的编程技术如何给程序员一个控制function的内部工作的能力，否则不可能重写和重新编译代码。 作为实验，使用这种技术来实现types推理algorithmW，从而产生对algorithm的干扰最小的错误消息。 这个示例程序的代码说明了这些概念的真正有用性以及它们可以轻松应用的方式。 还讨论了一些其他的实现技术和可能的应用，包括使用高阶函数来模拟exception和延续的使用。

这是一个伟大的论文; 任何对function编程感兴趣的人都可能喜欢阅读。

Answer 2

你可以看看在C＃中实现Y Combinator这个漂亮的post： recursionLambdaexpression式 ，它可能会帮助你更好地理解这个想法。

你可能想看看维基百科上的一些不错的文章： 定点组合和不动点定理

正如Nathan所说，许多function性技术都与Y组合有关，并且是有用的，所以请保持它！ Y真的很有用，因为它可以让你更好地理解你的代码，但是我觉得这不是特别有帮助。

Answer 3

你可以把combinator想象成运行你的函数的虚拟机，你用一个非recursion函数（=高阶函数）来描述它。

有时候，在程序控制下使用这个组合器，做类似于面向方面的编程（记忆，跟踪，…），但是我不知道的编程语言是允许的。 可能大部分时间太麻烦了，或者太难学习了。

Answer 4

其他人可以纠正我，如果我错了，但我很确定Y组合是严格的学术。 想想看：为了实现它，你的语言需要支持更高阶的函数，而不是recursion。 只有一种我认识的语言：lambda微积分。

因此，直到我们的机器从图灵机切换到lambda演算运行，Y组合将是严格的学术。

注意：与Y组合器相关的其他function性技术是有用的，所以请保持它。 了解Y组合器将帮助您了解延续，懒惰评估等。

Answer 5

let sprite = pipe4 sprite_start blanks (manyTill attribute newline) blanks (fun abc _ -> Sprite(a,c)) let sprites = let rec yfx = f (yf) x // The Y Combinator //let rec sprites_up = many1Indents sprite sprites_up |>> (fun x -> SubSprites x) // Does not work. let sprites_up = y (fun f -> many1Indents sprite f |>> (fun x -> SubSprites x)) many1Indents sprite sprites_up 

下面是我在F＃中编写的一个小型游戏库的编译器示例。 更具体地说，在上面我需要sprites_uprecursion调用自己，否则缩进parsing器将无法正常工作。

如果没有Y Combinator，我不可能正确地完成parsing器，而不得不求助于写这样的东西：

 let sprites_up4 = many1Indents sprite error |>> (fun x -> SubSprites x) let sprites_up3 = many1Indents sprite sprites_up4 |>> (fun x -> SubSprites x) let sprites_up2 = many1Indents sprite sprites_up3 |>> (fun x -> SubSprites x) let sprites_up1 = many1Indents sprite sprites_up2 |>> (fun x -> SubSprites x) let sprites_up = many1Indents sprite sprites_up1 |>> (fun x -> SubSprites x) 

Y Combinator真的不是一个很好的解决scheme，真的救了我。 这当然不是第一个想到的。