Doubly linked list - OCaml

OCaml

[edit]Imperative

type 'a dlink = {
  mutable data: 'a;
  mutable next: 'a dlink option;
  mutable prev: 'a dlink option;
}
 
let dlink_of_list li =
  let f prev_dlink x =
    let dlink = {
      data = x;
      prev = None;
      next = prev_dlink }
    in
    begin match prev_dlink with
    | None -> ()
    | Some prev_dlink ->
        prev_dlink.prev <- span=""> Some dlink
    end;
    Some dlink
  in
  List.fold_left f None (List.rev li)
;;
 
let list_of_dlink =
  let rec aux acc = function
  | None -> List.rev acc
  | Some{ data = d;
          prev = _;
          next = next } -> aux (d::acc) next
  in
  aux []
;;
 
let iter_forward_dlink f =
  let rec aux = function
  | None -> ()
  | Some{ data = d;
          prev = _;
          next = next } -> f d; aux next
  in
  aux
;;

# let dl = dlink_of_list [1;2;3;4;5] in
  iter_forward_dlink (Printf.printf "%d\n") dl ;;
1
2
3
4
5
- : unit = ()

[edit]Functional

The previous implementation is the strict equivalent of the other examples of this page and its task, but in regular OCaml these kind of imperative structures can be advantageously replaced by a functional equivalent, that can be use in the same area, which is to have a list of elements and be able to point to one of these. We can use this type:

type 'a nav_list = 'a list * 'a * 'a list

The middle element is the pointed item, and the two lists are the previous and the following items. Here are the associated functions:

let nav_list_of_list = function
  | hd::tl -> [], hd, tl
  | [] -> invalid_arg "empty list"
 
let current = function
  | _, item, _ -> item
 
let next = function
  | prev, item, next::next_tl ->
      item::prev, next, next_tl
  | _ ->
      failwith "end of nav_list reached"
 
let prev = function
  | prev::prev_tl, item, next ->
      prev_tl, prev, item::next
  | _ ->
      failwith "begin of nav_list reached"

# let nl = nav_list_of_list [1;2;3;4;5] ;;
val nl : 'a list * int * int list = ([], 1, [2; 3; 4; 5])
# let nl = next nl ;;
val nl : int list * int * int list = ([1], 2, [3; 4; 5])
# let nl = next nl ;;
val nl : int list * int * int list = ([2; 1], 3, [4; 5])
 
# current nl ;;
- : int = 3

http://rosettacode.org/wiki/Doubly-linked_list/Element_definition#OCaml