信息与OCaml的隐藏记录
问题描述:
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 []}
答
直接写入空是不是最容易在这样的数据结构,你需要编写插件,这将再次包含插入等一个......所以,让我们先写插入:
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)}
答
首先,它是bool,而不是布尔值。 :)
其次,这个定义相当麻烦。但是,你可以这样做:
let empty = {
insert=(fun x -> {
insert=(fun x -> assert false);
contains=(fun x-> assert false)});
contains=(fun x -> false)}
你插入的实现,并包含非空套代替“断言假”当然。
实现插入的提示,包含:不使用任何列表,使用现有和新集合中函数的组合。
你可以在例如W.Cook在“关于理解数据抽象,再次讨论”中指出,该论文可在线获取。
这很聪明,谢谢! – adelbertc