Skip to content

Instantly share code, notes, and snippets.

@scvalex
Created October 21, 2013 10:27
Show Gist options
  • Save scvalex/7081711 to your computer and use it in GitHub Desktop.
Save scvalex/7081711 to your computer and use it in GitHub Desktop.
An example of why polymorphic compare is tricky in OCaml.
(** A circular doubly-linked list in OCaml. See:
https://en.wikipedia.org/wiki/Doubly_linked_list#Circular_doubly-linked_lists
*)
module Doubly_linked_list = struct
type 'a doubly_linked_node = {
data : 'a;
mutable prev : 'a doubly_linked_node;
mutable next : 'a doubly_linked_node;
}
type 'a t = {
mutable head : 'a doubly_linked_node option;
}
(** [create ()] makes a new doubly-linked list. *)
let create () =
{ head = None; }
;;
(** [cons t data] prepends [data] to the doubly-linked
list [t]. *)
let cons t data =
let rec new_node =
{ data; prev = new_node; next = new_node; }
in
match t.head with
| None ->
t.head <- Some new_node
| Some node ->
new_node.next <- node;
new_node.prev <- node.prev;
new_node.next.prev <- new_node;
new_node.prev.next <- new_node;
t.head <- Some new_node
;;
(** [iter t ~f] executes [f] on each of the values
stored in the doubly-linked list [t]. *)
let iter t ~f =
let rec go ~start node =
f node.data;
if node.next <> start then
go ~start node.next
in
match t.head with
| None -> ()
| Some node -> go ~start:node node
;;
end
(* Create a doubly-linked list and print its contents. *)
let main () =
let list = Doubly_linked_list.create () in
Doubly_linked_list.cons list "3";
Doubly_linked_list.cons list "2";
Doubly_linked_list.cons list "1";
print_endline "Count-up timer go!";
Doubly_linked_list.iter list ~f:print_endline;
print_endline "Done!";
;;
let () = main ();;
@scvalex
Copy link
Author

scvalex commented Oct 21, 2013

Build and run with:

ocamlfind ocamlopt -o poly-compare poly_compare.ml && ./poly-compare

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment