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

Question

Как можно значение типа:

type Tree =
    | Node of int * Tree list

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

Полученное значение должно быть равно x в следующем коде Python для подходящего определения Tree:

x = Tree()
x.tlist = [x]

Редактировать : Очевидно, требуется больше объяснений. Я пытаюсь изучать F # и функциональное программирование, поэтому я решил реализовать дерево покрытия , которое я программировал ранее на других языках. Здесь важно то, что точки каждого уровня являются подмножеством точек уровня ниже. Структура концептуально переходит в уровень-бесконечность.

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

Answer 1

Ответ Томаса предлагает два возможных способа создания рекурсивных структур данных в 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 })

Answer 2

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

Однако 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

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