I'm wondering if it wouldn't be better to simply implement it using a mutable 2d Java array? (the standard imperative implementation).
It wouldn't be a 'purely functional' answer, but the array wouldn't leak out of the levenshtein-distance function. On Mar 22, 3:09 am, Christian Schuhegger <christian.schuheg...@gmail.com> wrote: > Hello all, > > I've implemented the levenshtein measure in clojure and am quite happy > with it except that I run into stack overflows if I hand over long > strings. My current solution looks like this: > -- snip start -- > (declare levenshtein-rec) > (declare change-cost) > (defn levenshtein > "Compute Levenshtein distance between 2 strings" > [a b] > (binding [change-cost (fn [x y] (if (= x y) 0 1)) > levenshtein-rec (memoize > (fn [x y] > (cond > (empty? x) (count y) > (empty? y) (count x) > :default > (min > (+ 1 (levenshtein-rec (rest x) y)) ; deletion > (+ 1 (levenshtein-rec x (rest y))) ; addition > (+ (change-cost (first x) (first y)) > (levenshtein-rec (rest x) (rest y))) ; > change > )) > ) > ) > ] > (levenshtein-rec a b))) > ;;;(levenshtein "kitten" "sitting") > ;;;(time (levenshtein (apply str (repeat 300 "kitten ")) (apply str > (repeat 300 "sitting")))) > -- snip end -- > > Now what I've done to overcome that limitation was to transform the > function from above manually into continuation passing style (CPS), > adapted it to be ready for trampolining (return in certain places > functions instead of evaluating them) and added memoization. The > result is extremely ugly and can be seen here:https://gist.github.com/880873 > > I did not look yet into the clojure libraries for automatic CPS > transformation, but I am nearly certain that these libraries will not > take care of adapting the result to be ready for trampolining and > definitely will not take care of memoization. > > Would somebody on the list have a proposal on how to create such a > solution simpler and nicer? Especially how would you apply memoization > easily in CPS style? > > I've found an article on the web where somebody did something in that > direction in > F#:http://www.patrickdewane.com/2009/02/continuation-passing-style-and-m... > > Many thanks and best regards, > Christian -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
