Information hiding with OCaml records

Question

Given

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

How can I implement

val empty : 'a set

?

I've tried closing over something, say a list, but the return type is wrong.. since it is. (ignoring the fact that the performance characteristics here are terrible :-) )

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

directly writing the empty is not the easiest in such data structure, as you will need to write the insert, which will contains again an insert and so one... So let's write first the 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) }

in insert, you want to recursively call insert, but the first parameter will be the record you are writing. So here is the complete solution:

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