F#: рекурсивное значение, которое может ссылаться на себя

Question

У меня есть запись:

type node = {
               content : string;
               parent : node option;
               branch : string option;
               children : seq<node> option;
            }

Который я хочу создать таким образом:

let rec treeHead = {
                       content = "Value"
                       parent = None;
                       branch = None;
                       children = tree (Some(treeHead)) rows;
                   };

куда

let rec tree (parent:node option) (rows:seq<CsvRow>) :seq<node> option

Рекурсивная функция, которая получает дочерние элементы узла (для построения дерева). Итак, как вы можете видеть, объект treeHead должен вызывать себя через функцию дерева.

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

Мой вопрос заключается в том, что treeHead вызывает ошибку и предупреждение. Ошибка говорит:

Значение treeHead будет оцениваться как часть его собственного определения.

И предупреждение говорит:

Эта и другие рекурсивные ссылки на определяемый объект (ы) будут проверены на предмет правильности инициализации во время выполнения посредством использования отложенной ссылки. Это потому, что вы определяете один или несколько рекурсивных объектов, а не рекурсивные функции. Это предупреждение может быть подавлено с помощью "#nowarn "40"или" --nowarn:40 ".

Во-первых, я делаю это правильно (я имею в виду, не учитывая изменчивый выбор)? И как мне это исправить.

Answer 1

Суть неизменяемых структур данных в том, что они неизменны. (<- некоторые вещи уровня Йоды прямо здесь)

С изменяемой структурой данных вы сначала создаете себе коробку, а затем начинаете помещать вещи в коробку. Одна из вещей, которую вы вставите, может быть ссылкой на саму коробку. Так как у вас уже есть коробка, это нормально, вы можете взять ее ссылку.

С неизменяемой структурой данных это не работает: вы должны перечислить все, что входит в блок, прежде чем блок даже существует! Так что сама коробка не может быть одной из этих вещей. Вот что говорит вам компилятор в сообщении об ошибке: the value foo would be evaluated as part of its own definition, Не могу сделать Невезение.

Если бы только вы могли обернуть ссылку на коробку таким образом, чтобы не оценивать ее сразу, а отложить оценку на потом, пока коробка не будет полностью построена... Я знаю! Поместите это в закрытие!

let getMe42 x = 42

type R1 = { r1: int }
let rec x1 = { r1 = getMe42 x1 }  // Doesn't work: the definition of `x1` references `x1` itself

type R2 = { r2: unit -> int }
let rec x2 = { r2 = fun() -> getMe42 x2 } // This works: the definition of `x2` only creates a _closure_ around `x2`, but doesn't reference it right away

Итак, если я могу создать лямбду, может я смогу обмануть компилятор, передав лямбду другой функции и вызвав ее сразу?

let getMe42 f = printfn "%O" <| f(); 42

type R = { r: int }
let rec x = { r = getMe42 (fun () -> x) }

> System.InvalidOperationException: ValueFactory attempted to access the Value property of this instance.

Черт! Сила сильна с этим. Хотя компилятор не может доказать, что я капризничаю во время компиляции, он ловко оборачивает инициализацию в Lazy<T>, так что я получаю ошибку во время выполнения.

Интересно, что в очень ограниченном случае простой вставки прямой ссылки на себя без сложной обработки это работает:

type R = { r: R }
let rec x = { r = x }  // Works just fine, not even a warning.

Вы даже можете пройти весь путь до черепах:

type R = { r: R }
let rec x = { r = { r = { r = { r = x } } } }  // Still works!

Это очень особый случай, для существования которого я не вижу разумного обоснования. Это работает, потому что F# компилирует вспомогательное поле как internalне private, что позволяет ему изменять поле после построения записи. Следствие состоит в том, что это будет работать только в той же сборке, где определен тип.

---

Рекурсивные значения - это одна из тех темных магий, которые требуют, чтобы вы разделили свою душу на две части. Я считаю, что правильный термин - хакрукс.

Не делай этого. Просто нет, хорошо? Возвращайся на светлую сторону, у нас тоже есть печенье.