Ocaml autoréférence

Question

J'ai créé type t = Test int * t ref

Comment créer un objet de type t?

Answer 1

Comme delnan dit, vous pouvez utiliser des valeurs cycliques:

let rec x = Test (0, ref x) 

Alors que récursion est généralement utilisé pour définir des fonctions, il est possible pour certaines valeurs. Ce n'est pas possible en général, il y a des restrictions décrites in the documentation. L'idée est que cette valeur est allouée par tas, donc il est facile de l'utiliser récursivement: allouer d'abord l'espace pour un constructeur "Test", puis vous pouvez définir son champ en utilisant pour "x" l'adresse du constructeur alloué, même s'il pointe vers une valeur non encore définie. Les fonctions, les valeurs paresseuses, les paires, les enregistrements, etc., suivent tous ce modèle. Bien sûr, la spécification n'est pas si bas niveau ("heap-assigned" n'est pas défini dans le manuel OCaml), il y a une spécification syntaxique légèrement plus restrictive.

Une fois que vous avez bootstrapped une valeur par récursion valeur, vous pouvez construire des valeurs plus élaborées:

let rec x = Test (0, ref x) 
let y = Test (1, ref x) 
let (Test (_, r)) = x in r := y 

Vous pouvez aussi le faire directement

let rec x = Test (0, ref y) 
and y = Test (1, ref x) 

Il est également possible, mais vraiment déconseillés , pour utiliser une "valeur fictive" produite par Obj. C'est ainsi que le module Queue de la bibliothèque standard est implémenté.

Un problème avec cette définition est que les valeurs sont cycliques. Cela peut être problématique si vous prévoyez d'itérer sur la «queue» de ces valeurs. Si vous envisagez d'utiliser le champ int pour garder trace de la "longueur de queue" de la structure (0 signifie que la référence est un pointeur fictif qui ne doit pas être suivi), c'est exactement la manière dont le module Queue est implémenté.

D'autres options sont possibles. Vous pouvez par exemple utiliser un modèle où la valeur NULL du pointeur de queue est explicité à l'aide d'un type d'option:

type t' = Test of int * t' option ref 

let x = Test (0, ref None) 
let y = Test (0, ref (Some x)) 

let rec length (Test (_, tail)) = 
    match !tail with 
    | None -> 0 
    | Some tl -> 1 + length tl 

Dans ce cas, vous n'avez pas besoin récursion pour amorcer votre type, None suffit. Bien sûr, comme les types d'options ont une indirection, cela revient à un coût de performance modéré.

PS: Notez que pour les types d'un constructeur comme celui-ci, vous pouvez être mieux avec un type d'enregistrement:

type t = { 
    field : int; 
    tail : t ref; 
}