如何在没有“let rec"的情况下定义 y 组合器? [英] How do I define y-combinator without "let rec"?

问题描述

在几乎所有示例中，ML 类型语言中的 y 组合器都是这样编写的:

In almost all examples, a y-combinator in ML-type languages is written like this:

let rec y f x = f (y f) x
let factorial = y (fun f -> function 0 -> 1 | n -> n * f(n - 1))

这按预期工作，但是使用 let rec ... 定义 y 组合器感觉像是在作弊.

This works as expected, but it feels like cheating to define the y-combinator using let rec ....

我想在不使用递归的情况下定义这个组合子，使用标准定义:

I want to define this combinator without using recursion, using the standard definition:

Y = λf·(λx·f (x x)) (λx·f (x x))

直接翻译如下:

let y = fun f -> (fun x -> f (x x)) (fun x -> f (x x));;

然而，F# 抱怨它无法确定类型:

However, F# complains that it can't figure out the types:

  let y = fun f -> (fun x -> f (x x)) (fun x -> f (x x));;
  --------------------------------^

C:UsersJulietAppDataLocalTempstdin(6,33): error FS0001: Type mismatch. Expecting a
    'a    
but given a
    'a -> 'b    
The resulting type would be infinite when unifying ''a' and ''a -> 'b'

如何在不使用 let rec ... 的情况下在 F# 中编写 y 组合器?

How do I write the y-combinator in F# without using let rec ...?

推荐答案

正如编译器所指出的，没有类型可以分配给 x 使得表达式 (xx) 是类型良好的(严格来说这不是正确的；您可以将 x 明确键入为 obj->_ - 请参阅我的最后一段).您可以通过声明递归类型来解决此问题，以便非常相似的表达式可以工作:

As the compiler points out, there is no type that can be assigned to x so that the expression (x x) is well-typed (this isn't strictly true; you can explicitly type x as obj->_ - see my last paragraph). You can work around this issue by declaring a recursive type so that a very similar expression will work:

type 'a Rec = Rec of ('a Rec -> 'a)

现在Y-combinator可以写成:

Now the Y-combinator can be written as:

let y f =
  let f' (Rec x as rx) = f (x rx)
  f' (Rec f')

不幸的是，您会发现这不是很有用，因为 F# 是一种严格的语言，因此，您尝试使用此组合器定义的任何函数都会导致堆栈溢出.相反，您需要使用 Y 组合子的应用顺序版本 (f.(xf(y.(xx)y))(xf(y.(xx)y))):

Unfortunately, you'll find that this isn't very useful because F# is a strict language, so any function that you try to define using this combinator will cause a stack overflow. Instead, you need to use the applicative-order version of the Y-combinator (f.(x.f(y.(x x)y))(x.f(y.(x x)y))):

let y f =
  let f' (Rec x as rx) = f (fun y -> x rx y)
  f' (Rec f')

另一种选择是使用显式惰性来定义正序 Y 组合子:

Another option would be to use explicit laziness to define the normal-order Y-combinator:

type 'a Rec = Rec of ('a Rec -> 'a Lazy)
let y f =
  let f' (Rec x as rx) = lazy f (x rx)
  (f' (Rec f')).Value

这样做的缺点是递归函数定义现在需要显式强制惰性值(使用 Value 属性):

This has the disadvantage that recursive function definitions now need an explicit force of the lazy value (using the Value property):

let factorial = y (fun f -> function | 0 -> 1 | n -> n * (f.Value (n - 1)))

但是，它的优点是您可以定义非函数递归值，就像在惰性语言中一样:

However, it has the advantage that you can define non-function recursive values, just as you could in a lazy language:

let ones = y (fun ones -> LazyList.consf 1 (fun () -> ones.Value))

作为最后一种选择，您可以尝试通过使用装箱和向下转换来更好地近似无类型 lambda 演算.这会给你(再次使用 Y 组合器的应用顺序版本):

As a final alternative, you can try to better approximate the untyped lambda calculus by using boxing and downcasting. This would give you (again using the applicative-order version of the Y-combinator):

let y f =
  let f' (x:obj -> _) = f (fun y -> x x y)
  f' (fun x -> f' (x :?> _))

这有一个明显的缺点，它会导致不必要的装箱和拆箱，但至少这完全是实现内部的，永远不会在运行时真正导致失败.

This has the obvious disadvantage that it will cause unneeded boxing and unboxing, but at least this is entirely internal to the implementation and will never actually lead to failure at runtime.

这篇关于如何在没有“let rec"的情况下定义 y 组合器?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！