Commits

camlspotter committed 9103db1

levenshtein

  • Participants
  • Parent commits fbc2b00

Comments (0)

Files changed (5)

 - Added scan*_left functions
 - Added Dllist for doubly linked list
 - Added Result in Spot
-- Added Base.{result, from_Ok, from_Result} 
+- Added Base.{result, from_Ok, from_Result, memoize_rec} 
+- Added String.Levenstein.dist_non_tco
 
 2.1.1
 ------------
     Hashtbl.replace cache v r;
     r
 
+let memoize_rec f =
+  let cache = Hashtbl.create 101 in
+  let rec g v = 
+    try Hashtbl.find cache v with Not_found ->
+      let r = f g v in
+      Hashtbl.replace cache v r;
+      r
+  in
+  g
+
 external (&) : ('a -> 'b) -> 'a -> 'b = "%apply"
 external (&~) : (f:'a -> 'b) -> 'a -> 'b = "%apply"
 external (|!) : 'a -> ('a -> 'b) -> 'b = "%revapply"
 val memoize : ('c -> 'd) -> 'c -> 'd
 (** Memozation by hash *)
 
+val memoize_rec : (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b
+(** Memozation by hash with fixed point. You can call memoized self inside:
+
+    memoize_rec (fun f -> .... f v ....) w
+ *)
+
 val time : ('a -> 'b) -> 'a -> 'b * float
 (** simple profiling *)
 
   fold acc from
     
 let foldi_left f acc s = scani_left f acc s
+
+module Levenshtein = struct
+  let (@) = String.unsafe_get
+
+  (* It is not tail recursive, but so far I am happy *)    
+  let dist_non_tco s1 s2 =
+    let lev lev_fix (i, j) = match i, j with
+      | -1, d | d, -1 -> max d 0
+      | _ ->
+          min (lev_fix (i-1, j) + 1)
+          & min (lev_fix (i, j-1) + 1)
+                (lev_fix (i-1, j-1) + if s1@i = s2@j then 0 else 1)
+    in
+    memoize_rec lev (String.length s1 - 1, String.length s2 - 1)
+end
 val foldi_left : 
   (int -> 'a -> char -> [< `Continue of 'a | `Stop of 'a]) 
   -> 'a -> string -> 'a
+
+module Levenshtein : sig
+  val dist_non_tco : string -> string -> int
+  (* Levenshtein edit distance. 
+     * Memoized.
+     * Non tail recursive. *)
+end