edit_distance.ml

open Js.String

module Ops = struct
  type t = 
    | Delete of string * int
    | Insert of string * string * int
    | Replace of string * string * int

  let run op = match op with
    | Delete (str, i) ->
      (slice ~from:0 ~to_:i str) ^ (sliceToEnd ~from:(i + 1) str)
    | Insert (str, char, i) -> 
      (slice ~from:0 ~to_:i str) ^ char ^ (sliceToEnd ~from:i str)
    | Replace (str, char, i) ->
      (slice ~from:0 ~to_:i str) ^ char ^ (sliceToEnd ~from:(i + 1) str)
end

let min = Js.Math.min_int
let min3 a b c = min (min a b) c
let max_safe_int = [%raw "Number.MAX_SAFE_INTEGER"]

let memoize f =
  let word = ref "" in
  let dict = ref (Js.Dict.empty ()) in
  let rec g w1 w2 p1 =
    if !word <> w2 then ( 
      dict := Js.Dict.empty ();
      word := w2;
    );
    match Js.Dict.get !dict w1 with
    | None ->
      let result = f g w1 w2 p1 in
      Js.Dict.set !dict w1 result;
      result
    | Some num -> num
  in g
  
let edit_distance = memoize (fun edit_distance w1 w2 idx ->
  if w1 = w2
    then 0
  else
    let (c1, c2) = (get w1 idx, get w2 idx) in
    if c1 = c2 
      then edit_distance w1 w2 (idx + 1)
    else
      let len1, len2 = length w1 - 1, length w2 - 1 in
      let open Ops in
      let delete = fun () -> 1 + edit_distance (run (Delete (w1, idx))) w2 idx in
      let insert = fun () -> 1 + edit_distance (run (Insert (w1, c2, idx))) w2 (idx + 1) in
      let replace = fun () -> 1 + edit_distance (run (Replace (w1, c2, idx))) w2 (idx + 1) in

      if idx > len1 then insert ()
      else if idx > len2 then delete ()
      else min3 (insert ()) (replace ()) (delete ()))