Implemented a set class as a naive unordered one-linked-list

Learning
1

Feel free to comment on my code.

2

Using an object for this is overkill. You can get the same semantics in a much simpler way, with a reference to a list:

type myintset = int list ref

let make () =
  ref []

let add set n =
  if not (List.mem n !set) then set := n :: !set

let print set =
  List.iter (fun n -> print_int n; print_newline ()) !set

let () =
  let s = make () in
  add s 1;
  add s 2;
  add s 3;
  add s 3;
  add s 2;
  add s 1;
  print s

Cheers,
Nicolas

1 Like
3

Thanks,
I’m thinking now of a “sorted-one-linked-list” & “balanced-binary-tree”.
But I’m totally clueless…

4

Balanced binary tree is the implementation used internally by Stdlib.Set, you can have a look at it to learn how it’s done, it’s not doing things that are too clever, so hopefully it doesn’t appear too complicated.