如何定义不带"let rec"的y-combinator? [英] 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-combinator一样.

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:\Users\Juliet\AppData\Local\Temp\stdin(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-combinator?

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

推荐答案

正如编译器指出的那样，没有可以分配给x的类型，因此表达式(x x)是正确类型的(这是' t严格正确；您可以将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组合器可以写为:

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.(\x.f(\y.(x x)y))(\x.f(\y.(x x)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-combinator?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！