cacher l'information avec OCaml enregistre

Question

Étant donné

type 'a set = { insert : 'a -> 'a set; contains : 'a -> bool } 

Comment puis-je mettre en œuvre

val empty : 'a set 

?

J'ai essayé de fermer sur quelque chose, disons une liste, mais le type de retour est faux .. car il l'est. (Sans tenir compte du fait que les caractéristiques de performance ici sont terribles :-))

let empty = 
    let rec insert_f set a = 
    match set with 
    | [] -> a :: [] 
    | k :: rest -> 
     if k = a then 
      k :: rest 
     else 
      k :: insert_f rest a 
    in 
    let rec contains_f set a = 
     match set with 
     | [] -> false 
     | k :: rest -> 
      if k = key then 
      true 
      else contains_f rest a 
    in 
     { insert = insert_f []; contains = contains_f []} 

Answer 1

écrit directement le vide est pas le plus facile dans une telle structure de données, car vous aurez besoin d'écrire l'insert, qui contient à nouveau un insert et donc un ... Alors Écrivons d'abord l'insert:

let rec insert : 'a set -> 'a -> 'a set = fun s x -> { 
    insert = (fun y -> failwith "TODO"); 
    contains = (fun y -> if x = y then true else s.contains y) } 

dans l'insertion, vous voulez appeler de manière récursive insert, mais le premier paramètre sera l'enregistrement que vous écrivez. Voici donc la solution complète:

let rec insert : 'a set -> 'a -> 'a set = fun s x -> 
    let rec ss = { 
    insert = (fun y -> insert ss y); 
    contains = (fun y -> if x = y then true else s.contains y)} 
    in ss 

let rec empty = { 
    insert = (fun x -> insert empty x); 
    contains = (fun x -> false)} 

Answer 2

Tout d'abord, il est bool, pas booléen. :)

Deuxièmement, cette définition est assez lourde. Mais vous pouvez faire quelque chose comme:

let empty = { 
    insert=(fun x -> { 
      insert=(fun x -> assert false); 
      contains=(fun x-> assert false)}); 
    contains=(fun x -> false)} 

avec vos implémentations d'insertion et contient des ensembles non vides en place de « assert false » bien sûr.

Un conseil pour implémenter insert et contient: n'utilisez pas de listes, utilisez des compositions de fonctions à partir d'ensembles existants et nouveaux.

Vous pouvez trouver de bons exemples, par ex. "Sur Understanding Data Abstraction, Revisited" par W. Cook, ce document est disponible en ligne.