A few things:
--clojure does not do automatic TCO, so you might want to look at
recur to handle your stack issue
--recur won't work unless you rewrite your function so that the
recursive call is in tail position
--you probably can do that rewrite by passing around the levenshtein
grid as an accumulator (not quite the same, or as hard to figure out,
as cps)
--once you have the simple recursive function with an accumulators for
the grid and the result, wrap that up in a function with only the
parameters you want to expose
--I am not sure this is a great use case for memoize--if your function
is properly recursive it will not take very long to run--but if you
want to use it, wrap the simple-signature function with memoize

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

Reply via email to