数字混じり文字列ソートをClojureで

面白そうな問題見付けたのでやってみた。
数字混じり文字列ソート ~ Rubyとの血みどろの闘い ~
元は、どう書く.org のちょっと前のネタみたい。

(use 'clojure.contrib.str-utils)

(defn apply-flip [f a b]
  (f b a))

(defn prepare [n xs]
  (->> xs
       (re-partition #"\d+")
       (apply-flip concat (repeat "0"))
       (take n) (partition 2)
       (mapcat (juxt first #(-> % second Integer/parseInt)))
       vec))

(defn mixed-sort [xs]
  (let [p (partial prepare (->> (map count xs) (apply max) inc))]
    (sort #(compare (p %1) (p %2)) xs)))

カオス。例によってシーケンス厨的なコード。if のような条件分岐を極力排除してるのもいつも通り。「Clojure ならでは」な小細工やバッドノウハウが何ヵ所かあります。結構頭つかった。
基本路線は早い段階で決るんだけど、その実現方法に変な色気を出してしまうのが悪い癖だ。自覚はある。

->> で処理を繋いでいると「引数の順序が逆ならなー」と思う状況によくなる。そんな時、上の apply-flip みたいな関数があると便利。clojure.core に入れといて欲い。

実行結果

(mixed-sort ["1.txt" "10.txt" "100.txt" "2.txt" "20.txt"])
;;=> ("1.txt" "2.txt" "10.txt" "20.txt" "100.txt")

(mixed-sort ["x12" "x13" "x1A" "x1B" "xAB"])
;;=> ("x1A" "x1B" "x12" "x13" "xAB")

(mixed-sort ["A10B1" "A10B10" "A10B2" "A1B1" "A1B10" "A1B2" "A2B1" "A2B10" "A2B2"])
;;=> ("A1B1" "A1B2" "A1B10" "A2B1" "A2B2" "A2B10" "A10B1" "A10B2" "A10B10")

バグってた

上の例題ではうまくいくけど、 \0 よりも文字コードが小さい文字が含まれると想定通りにいかない。
prepare で生成するコレクションを compare するときコレクションの要素数が同じでなければならないため、re-pertition したあとのコレクションの長さを全体の最大のものにあわせている。要素数の足りないコレクションに "0" を加えて調整しているのだが、これがマズイ。
(repeat "0") ではなく (cycle ["0" ""]) を concat して長さを合わせればよさそうだが、 "0" が先か "" が先かは対象データによって違ってしまう。結局そこで if が必要になるのかな。

解決した

(use 'clojure.contrib.str-utils
     'clojure.contrib.core)

(defn prepare [n xs]
  (->> xs
       (re-partition #"\d+")
       (apply-flip concat (repeat nil))
       (take n) (partition 2)
       (mapcat (juxt first #(-?> % second Integer/parseInt)))
       vec))

もういっそ、(repeat "0") じゃなく (repeat nil) にすりゃいいだろうと開き直り。nil だと parseInt で例外が起きるのでそこにかなり気を使っていたんだけど、最終手段として clojure.contrib.core/-?> にご登場頂いた。

というか

「最大の長さに合わせる」というところがかなり微妙だ。文字列の長さの最大でとってるけど、re-partition で分割されたコレクションは実際はもっと要素数がすくない。「十分」ではあるけど「必要十分」ではないね。
無駄が多いプログラムであった。