F# — рекурсия с анонимными записями

Не будет правильного синтаксиса, это просто невозможно.

Подумайте о том, каким будет возвращаемый тип f2. Поскольку это запись с полем Children, представляющим собой список одной и той же записи, она будет выглядеть примерно так:

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

Это бесконечный тип. Такого зверя не существует.

Вопрос: а Фёдор, очевидно элемент списка Children это точно такая же запись, не может быть просто так?

Ну, нет, нельзя сказать «точно такая же пластинка», потому что у нее нет названия. Компилятор будет выглядеть как "какая запись? точно так же, как что?"

С другой стороны, когда вы объявляете именованную запись, вы можете использовать ту же самую запись в качестве элемента списка, потому что теперь сама запись является «вещью». У него есть собственная идентичность, которая отделена от его содержания, поэтому на него можно ссылаться отдельно от него.

Я думаю, что сообщение об ошибке могло бы быть более ясным.

Я не думаю, что есть способ сделать анонимную запись рекурсивной. Проблема в том, что компилятор не может определить возвращаемый тип f2 и, следовательно, не может определить тип поля Children анонимной записи. Как люди, мы можем видеть, что создание рекурсивного типа решит проблему, но компилятор этого не знает.

Я согласен с ответом Федора и думаю, что было бы интересно копнуть немного глубже.

поэтому давайте сделаем это немного более явным

вот код, который вы написали, который работает

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  

этот тип не разрешен по причине, которую объяснил Федор, фактически компилятор попытается оценить этот псевдоним типа, заменив внутренний 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.

Утверждение Брайана о том, что не может быть способа сделать анонимный тип рекурсивным, хотя и не совсем верно, мы можем сделать это, если в рекурсивном определении есть некоторый именованный тип, например.

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 теперь определена в терминах рекурсивной анонимной записи, но нам пришлось внедрить именованный тип в рекурсию (и поэтому мы должны использовать конструктор данных D в нашей функции f2), проблема заключается в том, что существует не является анонимным (конечным) типом, который удовлетворяет вашему исходному определению функции, не то, чтобы он был, но компилятор не может его найти.

кажется, неясно, что касается статуса 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([])])])