Cómo crear un valor de estructura de datos recursivo en (funcional) F #?

Question

¿Cómo puede un valor de tipo:

type Tree = 
    | Node of int * Tree list 

tener un valor que las referencias en sí genera de una manera funcional?

El valor resultante debe ser igual a x en el siguiente código Python, para una definición adecuada de árbol:

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

Editar: Obviamente más explicación es necesaria. Estoy tratando de aprender F # y programación funcional, así que elegí implementar el cover tree que he programado anteriormente en otros idiomas. Lo relevante aquí es que los puntos de cada nivel son un subconjunto de los del siguiente nivel. La estructura conceptualmente va al nivel -infinito.

En idiomas imperativos, un nodo tiene una lista de hijos que se incluye a sí misma. Sé que esto puede hacerse imperativamente en F #. Y no, no crea un ciclo infinito dado el algoritmo del árbol de portada.

Answer 1

La respuesta de Tomás sugiere dos formas posibles de crear estructuras de datos recursivas en F #. Una tercera posibilidad es aprovechar el hecho de que los campos de registro son compatibles con la recursión directa (cuando se utiliza en el mismo conjunto en el que se define el registro). Por ejemplo, el código siguiente funciona sin ningún 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 } 

El uso de este tipo de lista en lugar de la incorporada en uno, podemos hacer su trabajo código:

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

Answer 2

No puede hacer esto directamente si la referencia recursiva no se retrasa (por ejemplo, envuelta en una función o en un valor diferido). Creo que la motivación es que no hay forma de crear el valor con referencias inmediatas "a la vez", por lo que sería incómodo desde el punto de vista teórico.

Sin embargo, F # admite valores recursivos; puede usarlos si la referencia recursiva se retrasa (el compilador F # generará luego un código que inicializa la estructura de datos y rellena las referencias recursivas). La forma más fácil es envolver el refernece dentro de un valor perezoso (función funcionaría también):

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

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

Otra opción es escribir esto usando mutación. Entonces también necesita hacer que su estructura de datos sea mutable. Por ejemplo, puede almacenar ref<Tree> en lugar de 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 

Como se mencionó James, si no se nos permite hacer esto, usted puede tener algunas propiedades agradables como que cualquier programa que recorre la estructura de datos terminará (porque la estructura de datos es limitada y no puede ser recursiva). Por lo tanto, tendrá que ser un poco más cuidadoso con los valores recursivos :-)