F# - Recursion with anonymous records-CodePudding

Given the following F# snippet:

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

The compiler complains in f2 but not in f1.

What would be the correct syntax for anonymous record (if it exists)?

CodePudding user response：

There won't be a correct syntax, this is just impossible.

Think about what would be the return type of f2. Since it's a record with a field Children that is a list of the same record, it would look something like this:

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

It's an infinite type. Such a beast doesn't exist.

Q: but Fyodor, obviously the element of the Children list is the exact same record, can't it just be that?

Well, no, there is no way to say "the exact same record", because it doesn't have a name. The compiler would be like "what record? exact same as what?"

When you declare a named record, on the other hand, you can use the very same record as element of the list, because now the record itself is a "thing". It has its own identity, which is separate from its content, so it can be referenced separately from it.

I think the error message could be clearer though.

CodePudding user response：

I don't think there's any way to make an anonymous record that's recursive. The problem is that the compiler can't infer the return type of f2, and hence can't infer the type of the anonymous record's Children field. As humans, we can see that making the type recursive would solve the problem, but the compiler doesn't know that.