信息与OCaml的隐藏记录

Question

鉴于

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

我如何能实现

val empty : 'a set 

？

我试过关闭一些东西，说一个列表，但返回类型是错误的..因为它是。 （忽略这里的性能特征是可怕的事实:-)）

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

直接写入空是不是最容易在这样的数据结构，你需要编写插件，这将再次包含插入等一个......所以，让我们先写插入：

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) } 

在插入时，要递归调用insert，但第一个参数将是您正在写入的记录。因此，这里是完整的解决方案：

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

首先，它是bool，而不是布尔值。 :)

其次，这个定义相当麻烦。但是，你可以这样做：

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

你插入的实现，并包含非空套代替“断言假”当然。

实现插入的提示，包含：不使用任何列表，使用现有和新集合中函数​​的组合。

你可以在例如W.Cook在“关于理解数据抽象，再次讨论”中指出，该论文可在线获取。