使用 OCaml 记录隐藏信息

Question

给出

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

我该如何实施

val empty : 'a set

?

我试过关闭某些东西，比如说一个列表，但是 return 类型是错误的..因为它是。（忽略这里的性能特征很糟糕的事实:-)）

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

首先，它是bool，不是boolean。 :)

其次，这个定义比较繁琐。但是你可以这样做：

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

用你的 insert 和 contains for non-empty sets 代替 "assert false" 当然。

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

您可以在例如"On Understanding Data Abstraction, Revisited" 作者 W. Cook，该论文可在线获取。

Answer 2

在这种数据结构中直接写空不是最简单的，因为你需要写插入，它会再次包含一个插入等等......所以让我们先写插入：

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中，你想递归调用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)}

使用 OCaml 记录隐藏信息

Information hiding with OCaml records

ocaml

records

record