Y-Combinator 实际示例

发布于 2024-07-20 14:45:17 字数 253 浏览 9 评论 0原文

我最近读了一些关于函数式编程的文章，并且正在尝试理解 Y-Combinator。据我所知，您可以使用 Y-Combinator 以不直接支持递归的语言有效地实现递归。然而，我可能使用的每种语言都已经支持递归，因此我不确定使用 Y-Combinator 对此有多大用处。

我缺少 Y-Combinator 使用的更好的实际示例吗？有人在实际生产代码中实际使用过吗？或者说使用 Y-Combinator 实际上只是一种令人费解的学术练习（尽管非常酷）。

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

菊凝晚露 2024-07-27 14:45:17

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

用于计算定点的 Y 组合器可以用标准 ML 表示。它经常被用作高阶函数强大功能的示例，但通常不被视为有用的编程结构。在这里，我们看看基于 Y 组合器和包装器的编程技术如何为程序员提供对函数内部工作的一定程度的控制，而如果不重写和重新编译代码，这是不可能实现的。作为实验，类型推断算法 W 是使用该技术实现的，以便在产生错误消息时对算法的干扰最小。此示例程序的代码说明了这些概念的真正有用性以及应用它们的简便性。还讨论了许多其他实现技术和可能的应用，包括使用高阶函数来模拟异常和延续的使用。

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

回复收藏 0 原文

蓝咒 2024-07-27 14:45:17

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

您可能想查看维基百科上的一些不错的文章：定点组合器和

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

回复收藏 0 原文

ぽ尐不点ル 2024-07-27 14:45:17

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

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

注意：与 Y 组合器相关的其他函数技术很有用，所以请坚持下去。理解 Y 组合器将帮助您理解延续、惰性求值等。

回复收藏 0 原文

你怎么这么可爱啊 2024-07-27 14:45:17

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

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

回复收藏 0 原文

不及他 2024-07-27 14:45:17

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 确实救了我。但这肯定不是我首先想到的事情。

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

Here is an example from the compiler for a smallish game library I am making in F#. More specifically, in the above I need to have the sprites_up recursively call itself otherwise the indentation parser would not work correctly.

Without the Y Combinator, I could not have done the parser properly and would have had to resort to writing something like this:

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)

Would not have been a great solution, the Y Combinator really saved me there. It was certainly not the first thing that came to mind though.

回复收藏 0 原文

~没有更多了~