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