40

我最近读了一些关于函数式编程的书，我正在尝试了解 Y-Combinator。我知道您可以使用 Y-Combinator 以不直接支持递归的语言有效地实现递归。但是，我可能使用的每种语言都已经支持递归，所以我不确定使用 Y-Combinator 会有多大用处。

是否有我缺少的 Y-Combinator 使用的更好的实际示例？有没有人在实际生产代码中实际使用过一个？或者使用 Y-Combinator 真的只是一个令人费解的学术练习（尽管很酷）。

4

5 回答 5

27

我不同意其他答案：定点 (Y) 组合器确实有实际应用，但要找到它们需要非常有想象力的头脑。就像布鲁斯麦克亚当一样。这是他的论文That About Wraps Up的摘要：

用于计算不动点的 Y 组合子可以用标准 ML 表示。它经常被用作高阶函数功能的示例，但通常不被视为有用的编程结构。在这里，我们将了解基于 Y 组合器和包装器的编程技术如何使程序员能够对函数的内部工作进行一定程度的控制，而这在不重写和重新编译代码的情况下是不可能实现的。作为一个实验，类型推断算法 W 是使用这种技术实现的，因此产生的错误消息对算法的干扰最小。此示例程序的代码说明了这些概念的真正有用性以及应用它们的难易程度。还讨论了许多其他实现技术和可能的应用，

这是一篇很棒的论文；任何对函数式编程感兴趣的人都可能会喜欢阅读它。

于 2009-05-16T00:43:02.947 回答
7

您可以查看这篇关于在 C# 中实现 Y Combinator 的漂亮帖子：递归 Lambda 表达式，它可能会帮助您更好地理解这个想法。

您可能想查看 Wikipedia 上的一些不错的文章：定点组合器和定点定理

正如 Nathan 所说，许多函数技术都与 Y 组合器相关并且很有用，所以坚持下去！Y 确实很有用，因为它可以让您更好地理解您的代码，但我认为这对于描述它如何提供帮助并不是特别有帮助。

于 2009-05-15T17:22:22.520 回答
4

如果我错了，其他人可以纠正我，但我很确定 Y 组合器是严格的学术性的。想一想：要实现它，您的语言需要支持高阶函数而不是递归。我只知道一种这样的语言：lambda calculus。

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

注意：与 Y 组合器相关的其他函数技术也很有用，因此请坚持使用。了解 Y 组合器将帮助您了解延续、惰性求值等。

于 2009-05-15T16:11:24.843 回答
4

您可以将组合器视为运行您的函数的虚拟机，您可以通过非递归函数（= 高阶函数）来描述它。

有时最好让这个组合器受程序控制，做与面向方面编程（记忆、跟踪等）类似的事情，但我所知道的任何编程语言都不允许这样做。可能大多数时候它太麻烦和/或太难学了。

于 2009-05-15T17:14:52.773 回答
2 
let sprite = pipe4 sprite_start blanks (manyTill attribute newline) blanks (fun a b c _ -> Sprite(a,c))

let sprites = 
    let rec y f x = f (y f) 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_up 递归调用自身，否则缩进解析器将无法正常工作。

如果没有 Y Combinator，我无法正确完成解析器，不得不求助于编写如下内容：

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 真的救了我。不过，这当然不是首先想到的。

于 2016-02-14T10:13:57.487 回答