F# 递归对象

Question

我是F#和函数式编程的新手。所以这可能是个愚蠢的问题，或者和 F#中的递归对象重复了，但我不知道。

下面是一个简单的斐波那契函数：

let rec fib n = 
    match n with
    | 0 -> 1
    | 1 -> 1
    | _ -> fib (n - 1) + fib (n - 2)

它的签名是 int -> int。

可以重写为：

let rec fib = 
    fun n ->
        match n with
        | 0 -> 1
        | 1 -> 1
        | _ -> fib (n - 1) + fib (n - 2)

它的签名是 (int -> int)（在 Visual Studio for Mac 中）。

那么这个与之前的有什么不同呢？

如果我再添加一行像这样的代码：

let rec fib = 
    printfn "fib" // <-- this line
    fun n ->
        match n with
        | 0 -> 1
        | 1 -> 1
        | _ -> fib (n - 1) + fib (n - 2)

这个IDE为我提供了一个警告：

警告FS0040：通过使用延迟引用，将在运行时检查此对象及其他递归引用的初始化完整性。这是因为您正在定义一个或多个递归对象而不是递归函数。可以通过使用“＃nowarn" 40“或”--nowarn:40“来抑制此警告。

这一行代码如何影响初始化？

“递归对象”是什么意思？我在文档中找不到相关解释。

更新

感谢您的回复，解释得非常好。

阅读了您的答案后，我对递归对象有了一些想法。

首先，我犯了一个错误，前两段代码片段具有相同的签名，int -> int；但最后一个签名为(int -> int)（请注意：在带有Ionide扩展的vscode中，这些签名具有不同的表示形式）。

我认为两个签名之间的差别在于，第一个签名表示它只是一个函数，而另一个签名表示它是一个函数的引用，即一个对象。

对于没有parameter-list的每个let rec something，它都是一个对象而不是函数，请参见definition函数，而第二个代码片段是一个例外，可能被编译器优化为函数。

一个例子：

let rec x = (fun () -> x + 1)() // same warning, says `x` is an recursive object

我能想到的唯一原因是编译器不够智能，它会因为递归对象而抛出警告，就像警告所示，

这是因为你定义了一个或多个递归对象，而不是递归函数

即使这种模式永远不会有任何问题。

let rec fib = 
    // do something here, if fib invoked here directly, it's definitely an error, not warning.
    fun n ->
        match n with
        | 0 -> 1
        | 1 -> 1
        | _ -> fib (n - 1) + fib (n - 2)

你对此有何看法？

- Wizr

Answer 1

“递归对象”就像递归函数一样，除了它们是对象而不是函数。

递归函数是引用自身的函数，例如：

let rec f x = f (x-1) + 1

递归对象类似于引用自身的函数，但它不是一个函数，例如：

let rec x = x + 1

上面的代码实际上无法编译通过。 F#编译器能够正确地确定问题并发出错误提示：The value 'x' will be evaluated as part of its own definition。显然，这样的定义是荒谬的：为了计算x，您需要已经知道x。无法计算。

但是让我们看看是否可以更聪明一些。如果我在lambda表达式中关闭x呢？

let rec x = (fun() -> x + 1) ()

在这里，我将x封装在一个函数中，并立即调用该函数。这个代码可以编译，但会出现一个警告——与您正在收到的警告相同，大概是关于“在运行时检查初始化完整性”的内容。

那么让我们来到运行时：

> let rec x = (fun() -> x + 1) ()
System.InvalidOperationException: ValueFactory attempted to access the Value property of this instance.

毫不意外，我们遇到了一个错误：原来在这个定义中，你仍然需要知道 x 才能计算 x - 就像使用 let rec x = x + 1 一样。

但是如果是这样的话，为什么它还能编译呢？好吧，恰巧的是，通常情况下，严格证明 x 在初始化期间是否会访问自身是不可能的。编译器只是聪明到足以注意到它可能会发生（这就是为什么它会发出警告），但不够聪明以证明它一定会发生。

因此，在这种情况下，除了发出警告之外，编译器还将安装运行时保护程序，以检查在访问 x 时是否已经被初始化。带有这种保护程序的编译代码可能如下所示：

let mutable x_initialized = false
let rec x = 
    let x_temp = 
        (fun() -> 
            if not x_initialized then failwith "Not good!"
            else x + 1
        ) ()
    x_initialized <- true
    x_temp

实际的编译代码当然看起来不同；如果您好奇，请使用ILSpy查看

在某些特殊情况下，编译器可以证明一种方式或另一种方式。在其他情况下，它无法证明，因此安装运行时保护：

// Definitely bad => compile-time error
let rec x = x + 1

// Definitely good => no errors, no warnings
let rec x = fun() -> x() + 1

// Might be bad => compile-time warning + runtime guard
let rec x = (fun() -> x+1) ()

// Also might be bad: no way to tell what the `printfn` call will do
let rec x = 
    printfn "a"
    fun() -> x() + 1

- Fyodor Soikin

---

我更新了我的问题，请看一下。 - Wizr

如果您有更多问题，请单独发布。通过更新进行沟通效率低下。 - Fyodor Soikin

抱歉，我认为它更像是一条评论，应该放在这里，但它太长了 :( 。而且这是基于你的答案得出的我的想法，我不知道如何用单独的问题通知你。 - Wizr

Answer 2

最后两个版本之间存在着重大的区别。请注意，在第一个版本中添加printfn调用不会生成警告，并且"fib"将在每次函数递归时打印：

let rec fib n =
  printfn "fib"
  match n with
  | 0 -> 1
  | 1 -> 1
  | _ -> fib (n - 1) + fib (n - 2)

> fib 10;;
fib
fib
fib
...
val it : int = 89

< p > printfn 调用是递归函数体的一部分。但第三/最终版本仅在定义函数时打印一次 "fib"，然后不再打印。

有什么区别吗？在第三个版本中，您不仅定义了一个递归函数，因为还有其他表达式创建了一个在 lambda 上形成闭包的递归对象。考虑这个版本：

let rec fib3 = 
  let x = 1
  let y = 2
  fun n ->
    match n with
    | 0 -> x
    | 1 -> x
    | _ -> fib3 (n - x) + fib3 (n - y)

fib3不是一个简单的递归函数；它捕获了x和y，形成了一个闭包（printfn版本也是一样，尽管只是副作用）。这个闭包就是警告中提到的“递归对象”。在每次递归中，x和y都不会被重新定义，它们属于根级别的闭包/递归对象。

来自相关问题/答案的描述：

因为[编译器]无法保证在初始化之前不会访问该引用

虽然这并不适用于你的特定示例，但编译器无法知道你是否做了一些无害的事情，还是在fib3定义中引用/调用lambda之前，fib3已经具有值/已经初始化。 这里有另一个很好的答案解释相同的内容。

- Taylor Wood

---

我更新了我的问题，请看一下。 - Wizr