F# - 匿名记录的递归

Question

给定以下 F# 片段：

type A(children: A list) = 
    member val P1 = ""
    member val P2 = ""
    member val Children = children

type B = {
    F1:string
    Children: B list
}

let rec f1 (a:A) = 
    {
        F1 = a.P1
        Children = a.Children |> List.map f1
    }

let rec f2 (a:A) = 
    {|
        F1 = a.P1
        Children = a.Children |> List.map f2 //Error
    |}

let a = A([A([A([])])])

f1 a
f2 a

////////////////////
Error   FS0001  Type mismatch. Expecting a
    'A -> 'a'    
but given a
    'A -> {| Children: 'a list; F1: string |}'    
The types ''a' and '{| Children: 'a list; F1: string |}' cannot be unified.Active

编译器在 f2 中抱怨，但在 f1 中没有。

匿名记录（如果存在）的正确语法是什么？

Answer 1

不会有正确的语法，这是不可能的。

想想 f2 的 return 类型。因为它是一个字段 Children 的记录，它是同一记录的列表，它看起来像这样：

{|
  F1: string
  Children: list<
    {|
      F1: string
      Children: list<
        {|
          F1: string
          Children: list<
            ...
          >
        |}
      >
    |}
  >
|}

无限类型。这样的野兽是不存在的

问：但是 Fyodor，显然 Children 列表的元素是完全相同的记录，难道不能就是这样吗？

嗯，不，没有办法说“完全相同的记录”，因为它没有名字。编译器会像“什么记录？和什么完全一样？”

另一方面，当您声明一个命名记录时，您可以使用完全相同的记录作为列表的元素，因为现在记录本身就是一个“东西”。它有自己的标识，与内容是分开的，所以可以单独引用。

我认为错误信息可能更清楚。

Answer 2

我认为没有任何方法可以创建递归的匿名记录。问题在于编译器无法推断出 f2 的 return 类型，因此无法推断出匿名记录的 Children 字段的类型。作为人类，我们可以看到使类型递归可以解决问题，但编译器不知道。

Answer 3

我同意 Fyodor 的回答，我认为深入挖掘可能会很有趣。

所以让它更明确一点

这是您编写的有效代码

type B = {
    F1:string
    Children: B list
}

let rec f1 (a:A) : B = 
    {
        F1 = a.P1
        Children = a.Children |> List.map f1
    }

然后您尝试使用匿名记录来构建等效问题，但让我们显式地这样做并使用类型别名告诉编译器我们期望的类型并查看它在哪里失败

type C = {| F1: string; Children: C list |} //Error is here

let rec f2 (a:A) : C = 
    {|
        F1 = a.P1
        Children = a.Children |> List.map f2 
    |}

所以这里的错误是在类型别名上

Severity    Code    Description Project File    Line    Suppression State
Error   FS0953  This type definition involves an immediate cyclic reference through an abbreviation F# Miscellaneous Files

由于 Fyodor 解释的原因，这种类型是不允许的，实际上编译器会尝试通过用类型别名定义替换内部 C 来评估这种类型别名，显然这永远不会终止。（这种情况在其他但不是所有语言中很常见）。这个问题不仅限于匿名记录，还包括任何递归类型别名，例如

type Foo = Foo -> Foo

通常的做法是为类型指定一个显式名称，因此通常将内部表达式包装在数据构造函数中（请注意，这现在不再是类型别名）。

type C = C of {| F1: string; Children: C list |}

let rec f2 (a:A) : C = 
    {|
        F1 = a.P1
        Children = a.Children |> List.map f2
    |}
    |> C

并且这个类型基本上等同于明确命名的类型B。

Brian 关于可能没有办法使匿名类型递归的断言虽然不太正确，但只要在递归定义中有一些命名类型，我们就可以这样做，例如

type C<'a> = {| F1: string; Children: 'a list |}

type D = D of C<D>

let rec f2 (a:A) : C<D> = 
    {|
        F1 = a.P1
        Children = a.Children |> List.map (f2 >> D)
    |}

我们的 f2 函数现在是根据递归匿名记录定义的，但是我们必须将命名类型注入递归（因此我们必须在我们的 f2 函数中使用数据构造函数 D），问题是没有满足您原始函数定义的匿名（有限）类型，不是有，而是编译器找不到它。

C的状态好像不清楚

如果我们输入这个

let x : C<D> = {| F1=""; Children=[] |}

x.GetType();;

它回复了 FSI

val it: System.Type =
  <>f__AnonymousType3901454931`2[Microsoft.FSharp.Collections.FSharpList`1[FSI_0002+D],System.String]....

即C 是类型 {| 的匿名类型F1：字符串；儿童：D 名单 |}

当然，我们可以完全省去这个别名，例如

type D = D of {| F1: string; Children: D list |}

let rec f2 (a:A) : {| F1: string; Children: D list |} = 
    {|
        F1 = a.P1
        Children = a.Children |> List.map (f2 >> D)
    |}

let x = f2 <| A([A([A([])])])

F# - 匿名记录的递归

F# - Recursion with anonymous records

recursion

f#