scvalex · October 21, 2013 10:27 · Oct 21, 2013
diff --git a/poly_compare.ml b/poly_compare.ml
@@ -0,0 +1,63 @@
+(** 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 ();;
No results found