Come creare un valore di struttura dati ricorsivo in (funzionale) F #?

Question

Come può un valore di tipo:

type Tree = 
    | Node of int * Tree list 

avere un valore che fa riferimento sé generato in modo funzionale?

Il valore risultante dovrebbe essere uguale a x nel seguente codice Python per un adeguato definizione di albero:

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

Edit: Ovviamente più spiegazione è necessaria. Sto cercando di imparare F # e la programmazione funzionale, quindi ho scelto di implementare lo cover tree che ho programmato prima in altre lingue. La cosa rilevante qui è che i punti di ogni livello sono un sottoinsieme di quelli del livello sottostante. La struttura concettualmente va al livello -infinità.

In lingue imperative un nodo ha una lista di bambini che include se stessa. So che questo può essere fatto imperativamente in F #. E no, non crea un ciclo infinito dato l'algoritmo dell'albero della copertura.

Answer 1

La risposta di Tomas suggerisce due possibili modi per creare strutture dati ricorsive in F #. Una terza possibilità consiste nel trarre vantaggio dal fatto che i campi dei record supportano la ricorsione diretta (se utilizzata nello stesso assembly in cui è definito il record). Per esempio, il seguente codice funziona senza alcun problema:

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

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

Usando questo tipo di elenco invece del built-in uno, siamo in grado di rendere il vostro lavoro Codice:

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

Answer 2

Non è possibile eseguire questa operazione direttamente se il riferimento ricorsivo non viene ritardato (ad esempio, avvolto in una funzione o un valore lazy). Penso che la motivazione sia che non c'è modo di creare il valore con riferimenti immediati "alla volta", quindi questo sarebbe imbarazzante dal punto di vista teorico.

Tuttavia, F # supporta i valori ricorsivi - è possibile utilizzare quelli se il riferimento ricorsivo è ritardato (il compilatore F # genererà quindi del codice che inizializza la struttura dati e riempie i riferimenti ricorsivi). Il modo più semplice è quello di avvolgere la refernece all'interno un valore pigro (funzione avrebbe funzionato troppo):

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

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

Un'altra opzione è quella di scrivere questo utilizzando mutazione. Quindi è anche necessario rendere mutevole la struttura dei dati. Ad esempio è possibile memorizzare ref<Tree> invece di 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 

Come James detto, se non ti è permesso di fare questo, si può avere alcune proprietà piacevoli come ad esempio che qualsiasi programma che cammina la struttura dei dati terminerà (perché il data-structrue è limitato e non può essere ricorsivo). Quindi, dovrai essere un po 'più attento con i valori ricorsivi :-)