Y组合器实例

我不同意其他答案: 定点(Y)组合器 做 有实际应用 但是要找到它们需要一个非常富有想象力的头脑。像布鲁斯·麦卡丹。这是他的论文摘要 That About Wraps it Up :

用于计算不动点的y组合可以用标准的ml表示,它经常被用作高阶函数的幂的一个例子,但一般不被认为是一种有用的编程构造。在这里,我们来看一个基于Y组合器和包装器的编程技术如何给程序员一个在不重写和重新编译代码的情况下不可能实现的函数内部工作的控制级别。作为实验,利用该技术实现了类型推理算法W,使产生的错误信息对算法的干扰最小。这个示例程序的代码说明了这些概念的真正用途以及它们的易用性。还讨论了其他一些实现技术和可能的应用,包括使用高阶函数来模拟异常和延续的使用。

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

你可以看看这篇关于在C中实现Y组合器的漂亮文章: Recursive Lambda Expressions 它可能会帮助你更好地理解这个想法。

你可能想看看维基百科上的一些好文章: Fixed point combinator 和 Fixed point theorems

正如内森所说,许多功能性技术都与Y组合器有关,并且很有用,所以请继续努力!Y非常有用,因为它可以让您更好地理解代码,但我认为这对于描述它的帮助没有特别的帮助。

可以将组合器看作运行函数的虚拟机,用非递归函数(=higher-order函数)来描述。

有时,让这个组合器在程序控制下进行类似于面向方面编程(内存化、跟踪等)的工作是很好的,但是我所知道的编程语言不允许这样做。可能大多数时候它太笨重和/或太难学习。

如果我错了,其他人可以纠正我,但我很确定Y组合器是严格学术的。考虑一下:要实现它,您的语言需要支持高阶函数,而不是递归。我只知道一种语言:lambda微积分。

因此,在我们的机器从图灵机转换到运行lambda微积分之前,Y组合器将是严格学术的。

注:与Y组合器有关的其它功能技术 是 很有用,所以继续努力。了解Y组合器将帮助您理解连续性、延迟评估等。

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递归地调用自己,否则缩进解析器将无法正常工作。

如果没有Y组合器,我就无法正确地完成解析器的工作,因此不得不编写如下内容:

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组合器真的救了我。但这肯定不是第一件想到的事。