F# - Recursion with anonymous records

Question

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)?

Answer 1

I agree with Fyodor's answer and I think it may be interesting to dig a bit deeper.

so lets make it a bit more explicit

here is the code that you wrote that works

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

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

you then try to use an anonymous record to construct the equivalent issue, but lets do it explicitly and tell the compiler the type we expect using type aliases and see where it fails

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 
    |}

so the error here is on the type alias

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

this type isnt allowed for the reason Fyodor explained, effectively the compiler would try to evaluate this type alias by replacing the inner C with the type alias definition and clearly this would never terminate. (this scenario is quite common in other, but not all, languages). This problem isn't just isolated to anonymous records, but any recursive type alias e.g.

type Foo = Foo -> Foo

The normal route out is to give the type an explicit name so usually wrapping the inner expression in a data constructor (note this is now no longer a type alias).

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

and this type is basically equivalent to the explicitly named type B.

Brian's assertion that there may not be a way to make an anonymous type recursive though isnt quite correct, we can do this as long as there is some named type in the recursive definition e.g.

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)
    |}

our f2 function is now defined in terms of a recursive anonymous record, but we've had to inject a named type into the recursion (and thus we have to use the data constructor D in our f2 function), the issue though IS that there is no anonymous (finite) type that satisfies your original function definition, not that there is, but the compiler can't find it.

---

it seems to be unclear as to the status of C

if we type this

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

x.GetType();;

into FSI it replied

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

i.e. C is an anonymous type of type {| F1: string; Children: D list |}

we can, of course, completely dispense with this alias e.g.

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([])])])

Answer 2

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.

Answer 3

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.