読者です 読者をやめる 読者になる 読者になる

Arantium Maestum

プログラミング、囲碁、読書の話題

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は便利。だがやり過ぎるとちょっと可読性に難あり。積極的に試してみてバランスをとっていきたい。