Clojureでマージソート

なんとなくやってみた。

(defn merge
  ([col] col)
  ([[head1 & rest1 :as col1] [head2 & rest2 :as col2]]
   (cond (some empty? [col1 col2]) (concat col1 col2)
         (< head1 head2)
           (lazy-seq (cons head1 (merge rest1 col2)))
         :else
           (lazy-seq (cons head2 (merge col1 rest2))))))

(defn merge-couples [col]
  (if (= 1 (count col))
    (first col)
    (recur (map #(apply merge %) (partition-all 2 col)))))

(defn merge-sort [col]
  (merge-couples (for [x col] [x])))

わかったこと：

1. partitionは端数切り捨て
2. 端数切り捨てを避けるためにpaddingを空のリストにするとpartition-allと同じ挙動になる。
3. 実際に端数で([1 2 8] [])などと空のリストを返して欲しい時は残念な挙動（今回はmergeのarityを修正することで対応）
4. merge-couplesはiterateでも書けるが、recurで書く方が簡潔で読みやすい。こういうこともあるのか、と感心。
5. destructuringは便利。だがやり過ぎるとちょっと可読性に難あり。積極的に試してみてバランスをとっていきたい。