Как создать значение рекурсивной структуры данных в (функциональном) F#?

Ответ Томаса предлагает два возможных способа создания рекурсивных структур данных в F#. Третья возможность — воспользоваться тем фактом, что поля записи поддерживают прямую рекурсию (при использовании в той же сборке, в которой определена запись). Например, следующий код работает без проблем:

type 'a lst = Nil | NonEmpty of 'a nelst
and 'a nelst = { head : 'a; tail : 'a lst }

let rec infList = NonEmpty { head = 1; tail = infList }

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

type Tree = Node of int * Tree lst
let rec x = Node(1, NonEmpty { head = x; tail = Nil })

Вы не можете сделать это напрямую, если рекурсивная ссылка не задержана (например, обернута в функцию или ленивое значение). Я думаю, мотивация в том, что нет возможности создать значение с непосредственными ссылками "сразу", так что это было бы неудобно с теоретической точки зрения.

Однако F# поддерживает рекурсивные значения — вы можете использовать их, если рекурсивная ссылка задерживается (компилятор F# затем сгенерирует некоторый код, который инициализирует структуру данных и заполняет рекурсивные ссылки). Самый простой способ - обернуть ссылку внутри ленивого значения (функция тоже будет работать):

type Tree = 
    | Node of int * Lazy<Tree list>

// Note you need 'let rec' here!        
let rec t = Node(0, lazy [t; t;])

Другой вариант — написать это с помощью мутации. Затем вам также нужно сделать вашу структуру данных изменчивой. Например, вы можете сохранить ref<Tree> вместо Tree:

type Tree = 
    | Node of int * ref<Tree> list

// empty node that is used only for initializataion
let empty = Node(0, [])
// create two references that will be mutated after creation    
let a, b = ref empty, ref empty

// create a new node
let t = Node(0, [a; b])
// replace empty node with recursive reference
a := t; b := t

Как упомянул Джеймс, если вам не разрешено это делать, у вас могут быть некоторые приятные свойства, такие как то, что любая программа, которая проходит по структуре данных, завершится (поскольку структура данных ограничена и не может быть рекурсивной). Итак, вам нужно быть немного осторожнее с рекурсивными значениями :-)