Calculate levenshtein distance between two sequences.

levenshtein.clj

(defn levenshtein
  "Calculate levenshtein distance between two sequences."
  {:test #(are [d s1 s2] (= d (levenshtein s1 s2))
               0 "soup" "soup"
               3 "kitten" "sitting"
               3 "sitting" "kitten"
               0 [1 2 3] [1 2 3]
               1 [1 2 3] [1 2 3 4])}
  [s1 s2]
  (((reduce (fn [d [i j]]
              (assoc d (inc j)
                     (assoc (d (inc j)) (inc i)
                            (first
                             (sort
                              (list (+ (if (= (nth s1 i)
                                              (nth s2 j)) 0 1) ((d j) i))
                                    (inc ((d (inc j)) i))
                                    (inc ((d j) (inc i)))))))))
            (merge {0 (let [s (range (inc (count s1)))]
                        (zipmap s s))}
                   (let [s (range 1 (inc (count s2)))]
                     (zipmap s (map (fn [i] {0 i}) s))))
            (for [i (range 0 (count s1)) j (range 0 (count s2))] [i j]))
    (count s2))
   (count s1)))