let trimin x y z = min x (min y z);; class virtual ['a] edit_distance first_item second_item = object(ed) val f = (first_item: 'a) val s = (second_item: 'a) val mutable calced = false val mutable matrix = ([|[||]|] : int array array) method private gen_matrix f_size s_size = matrix <- Array.make_matrix (f_size + 1) (s_size + 1) 0; Array.iteri (fun i _ -> matrix.(0).(i) <- i) matrix.(0); Array.iteri (fun i row -> row.(0) <- i) matrix; method private update_matrix x y cost = let lowest = trimin (1 + matrix.(x).(y-1)) (1 + matrix.(x-1).(y)) (cost + matrix.(x-1).(y-1)) in matrix.(x).(y) <- lowest method virtual private cost_to_change: int -> int -> int method private calc () = if (not calced) then for ri = 1 to (Array.length matrix - 1) do for ci = 1 to (Array.length matrix.(0) - 1) do let cost = ed#cost_to_change (ri - 1) (ci - 1) in ed#update_matrix ri ci cost done done; calced <- true method distance () = ed#calc (); matrix.(Array.length matrix - 1).(Array.length matrix.(0) - 1) end;; class string_edit_distance x y = object(sed) inherit ['a] edit_distance x y method private cost_to_change i j = if f.[i] = s.[j] then 0 else 1 initializer sed#gen_matrix (String.length x) (String.length y) end;;