Data Structures in ReasonML: #5 Linked List

LinkedList.re

exception Empty_list;

module type LinkedList = {
  type t;
  type linkedList('t) =
    | Empty
    | List('t, linkedList('t));
  let empty: linkedList('t);
  let head: linkedList('t) => 't;
  let tail: linkedList('t) => linkedList('t);
  let insert: ('t, linkedList('t)) => linkedList('t);
  let remove: ('t, linkedList('t)) => linkedList('t);
  let contains: ('t, linkedList('t)) => bool;
  let iter: ('t => unit, linkedList('t)) => unit;
  let map: ('a => 'b, linkedList('a)) => linkedList('b);
  let fold: ('a => 'b, 'b, linkedList('a)) => 'b;
  let toArray: linkedList('t) => list('t);
  let isEmpty: linkedList('t) => bool;
  let size: linkedList('t) => int;
};

module LinkedList = {
  type t;
  type linkedList('t) =
    | Empty
    | List('t, linkedList('t));
  let empty = Empty;
  let head = list =>
    switch (list) {
    | Empty => raise(Empty_list)
    | List(head, _tail) => head
    };
  let tail = list =>
    switch (list) {
    | Empty => Empty
    | List(_head, tail) => tail
    };
  let rec insert = (value, list) =>
    switch (list) {
    | Empty => List(value, Empty)
    | List(head, tail) => List(head, insert(value, tail))
    };
  let rec remove = (value, list) =>
    switch (list) {
    | Empty => Empty
    | List(_head, Empty) => Empty
    | List(head, List(nextHead, nextTail) as tail) =>
      if (head === value) {
        List(nextHead, nextTail);
      } else {
        List(head, remove(value, tail));
      }
    };
  let rec contains = (value, list) =>
    switch (list) {
    | Empty => false
    | List(head, tail) =>
      if (head === value) {
        true;
      } else {
        contains(value, tail);
      }
    };
  let rec iter = (fn, list) =>
    switch (list) {
    | Empty => ()
    | List(head, Empty) => fn(head)
    | List(head, tail) =>
      fn(head) |> ignore;
      iter(fn, tail);
    };
  let rec map = (fn, list) =>
    switch (list) {
    | Empty => Empty
    | List(head, tail) => List(fn(head), map(fn, tail))
    };
  let rec fold = (fn, acc, list) =>
    switch (list) {
    | Empty => acc
    | List(head, tail) => fold(fn, fn(acc, head), tail)
    };
  let toArray = list =>
    fold((acc, a) => Array.concat([acc, [|a|]]), [||], list);
  let isEmpty = list =>
    switch (list) {
    | Empty => true
    | _ => false
    };
  let size = list =>
    switch (list) {
    | Empty => 0
    | _ =>
      let count = ref(0);
      iter((_) => count := count^ + 1, list);
      count^;
    };
};

let run = () => {
  open LinkedList;
  let t = insert(5, LinkedList.empty);
  let t = insert(15, t);
  let t = insert(2, t);
  Js.log2("to array: ", toArray(t));
  Js.log2("head: ", head(t) |> string_of_int);
  Js.log2("tail: ", tail(t) |> toArray);
  Js.log2("tail > head: ", tail(t) |> head |> string_of_int);
  let t = insert(4, t);
  Js.log2("to array: ", toArray(t));
  let t = remove(5, t);
  Js.log2("head: ", head(t) |> string_of_int);
  Js.log2("tail > head: ", tail(t) |> head |> string_of_int);
  Js.log2("contains 2", contains(2, t) === true);
  Js.log2("does not contain 5", contains(5, t) === false);
  Js.log2("to array: ", toArray(t));
  Js.log("iterate over the LinkedList: ");
  LinkedList.iter(a => Js.log2("Node value: ", a), t);
  Js.log2("is empty?", isEmpty(t));
  let t = map(a => a + 1, t);
  Js.log2("head: ", head(t) |> string_of_int);
  Js.log2("tail > head: ", tail(t) |> head |> string_of_int);
  Js.log2("size: ", size(t));
  Js.log2("to array: ", toArray(t));
  Js.log2("fold: sum == 24", fold((acc, a) => acc + a, 0, t) === 24);
};

run();