OCaml versions of an "unscientific benchmark" treap; first one translated from the Rust version, and the second more idiomatic OCaml in a functional style. See: https://github.com/frol/completely-unscientific-benchmarks

benchtreap1.ml

(* Translated from Rust version at https://github.com/frol/completely-unscientific-benchmarks *)

type nodecell = node option
and  node =
  { x: int;
    y: int;
    mutable left: nodecell;
    mutable right: nodecell }

module Node = struct
  let create x =
    { x;
      y = Random.bits ();
      left = None;
      right = None }
end

let rec merge lower greater =
  match lower,greater with
  | None, greater -> greater
  | lower, None -> lower
  | Some lower_node, Some greater_node ->
    if lower_node.y < greater_node.y then begin
      lower_node.right <- merge lower_node.right greater;
      lower
    end else begin
      greater_node.left <- merge lower greater_node.left;
      greater
    end

let rec split_binary orig value =
  match orig with
  | Some orig_node ->
    if orig_node.x < value then begin
      let split_pair = split_binary orig_node.right value in
      orig_node.right <- fst split_pair;
      orig, snd split_pair
    end else begin
      let split_pair = split_binary orig_node.left value in
      orig_node.left <- snd split_pair;
      fst split_pair, orig
    end
  | None -> None, None

let merge3 lower equal greater =
  merge (merge lower equal) greater


type split_result =
  { lower: nodecell;
    equal: nodecell;
    greater: nodecell }

let split orig value =
  let lower, equal_greater = split_binary orig value in
  let equal, greater = split_binary equal_greater (value+1) in
  { lower; equal; greater }


module Tree = struct
  type t = nodecell

  let create () = ref None

  let has_value self x =
    let splited = split !self x in
    self := merge3 splited.lower splited.equal splited.greater;
    if splited.equal = None then false else true

  let insert self x =
    let splited = split !self x in
    self := merge3
        splited.lower
        (if splited.equal = None then Some (Node.create x) else splited.equal)
        splited.greater

  let erase self x =
    let splited = split !self x in
    self := merge splited.lower splited.greater
end


let () =
  Random.init 5;
  let tree = Tree.create () in
  let cur = ref 5 in
  let res = ref 0 in
  for i = 1 to 1_000_000 do
    cur := (!cur * 57 + 43) mod 10007;
    match i mod 3 with
    | 0 -> Tree.insert tree !cur
    | 1 -> Tree.erase tree !cur
    | 2 -> if Tree.has_value tree !cur then incr res
    | _ -> failwith "Invalid command number (be sure the modulus matches the number of 'commands' handled)."
  done;
  print_int !res

benchtreap2.ml

(* This version implements a persistent treap: instead of using mutable "pointers", new values are returned. It's less awkward than benchtreap1.ml. *)

type node = { x: int; y: int; left: node option; right: node option }

let newnode x = { x; y = Random.bits (); left = None; right = None }

let rec merge lower greater =
  match lower,greater with
  | None, greater -> greater
  | lower, None -> lower
  | Some lower_node, Some greater_node ->
    if lower_node.y < greater_node.y then
      Some { lower_node with right = merge lower_node.right greater }
    else
      Some { greater_node with left = merge lower greater_node.left }

let split_binary orig value =
  let rec split = function
  | Some node ->
    if node.x < value then
      let a,b = split node.right in
      Some {node with right = a}, b
    else
      let a,b = split node.left in
      a, Some {node with left = b}
  | None -> None, None
  in
  split orig

let merge3 lower equal greater =
  merge (merge lower equal) greater


type split_result = { lower: node option; equal: node option; greater: node option }

let split orig value =
  let lower, equal_greater = split_binary orig value in
  let equal, greater = split_binary equal_greater (value+1) in
  { lower; equal; greater }


module Tree = struct
  type t = node option

  let empty : t = None

  let has_value self x =
    let splited = split self x in
    if splited.equal = None then false else true

  let insert self x =
    let splited = split self x in
    merge3
      splited.lower
      (if splited.equal = None then Some (newnode x) else splited.equal)
      splited.greater

  let erase self x =
    let splited = split self x in
    merge splited.lower splited.greater
end


let () =
  Random.init 5;

  let rec loop tree cur res i =
    if i >= 1_000_000 then res
    else begin
      let cur = (cur * 57 + 43) mod 10007 in
      let tree,res =
        match i mod 3 with
        | 0 -> Tree.insert tree cur, res
        | 1 -> Tree.erase tree cur, res
        | 2 -> tree, if Tree.has_value tree cur then res+1 else res
        | _ -> failwith "Invalid command number (be sure the modulus matches the number of 'commands' handled)."
      in loop tree cur res (i+1)
    end
  in

  let res = loop Tree.empty 5 0 1 in
  print_int res