Как создать рекурсивную стоимость структуры данных в (функциональном) F#?
Как может значение типа:
type Tree =
| Node of int * Tree list
имеет значение, который ссылки само генерировали функциональным способом?
Получающееся значение должно быть равно x в следующем коде Python для подходящего определения Дерева:
x = Tree()
x.tlist = [x]
Править: Очевидно, больше объяснения необходимо. Я пытаюсь изучить F# и функциональное программирование, таким образом, я принял решение реализовать дерево покрытия, которое я запрограммировал прежде на других языках. Соответствующая вещь здесь состоит в том, что точки каждого уровня являются подмножеством тех из уровня ниже. Структура концептуально идет для выравнивания - бесконечность.
На императивных языках узел имеет список детей, который включает себя. Я знаю, что это может быть сделано обязательно в F#. И не, это не создает бесконечный цикл, учитывая алгоритм дерева покрытия.
2 ответа
Ответ Томаса предлагает два возможных способа создания рекурсивных структур данных в 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 :
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
Как сказал Джеймс, если вам не разрешено это делать, вы можете иметь некоторые приятные свойства, такие как что любая программа, которая просматривает структуру данных, будет завершена (потому что структура данных ограничена и не может быть рекурсивной). Итак, с рекурсивными значениями нужно быть немного осторожнее: -)