2012年9月22日土曜日

Haskell入門書的クイックソート

Haskellの入門書に乗っていそうなクイックソートをClojureとCommon Lispで書いてみます。

- Clojure
;; defnやletで分配束縛ができます
;; group-byで関数を適用した結果の値によってグループ分けができます
;; ハッシュテーブル(map)は指定されたキーに対応する値を取得する関数にもなります
(defn qsort [cmp [piv & rst :as coll]]
  (if (empty? coll) []
    (#(concat (qsort cmp (%1 true)) [piv] (qsort cmp (%1 false)))
     (group-by #(boolean (cmp %1 piv)) rst))))

- Common Lisp
;; remove-if-not (filter)
(defun qsort-1 (cmp lst)
  (when lst
    (destructuring-bind (piv &rest rest) lst
      (flet ((f (x) (funcall cmp x piv)))
 (append (qsort-1 cmp (remove-if-not #'f rest))
  (list piv)
  ;; (remove-if-not (complement #'f) rest)
  (qsort-1 cmp (remove-if #'f rest)))))))

;; loopマクロ
(defun qsort-2 (cmp lst)
  (when lst
    (loop
       :with piv = (first lst)
       :for x in (rest lst)
       :if (funcall cmp x piv)
       :collect x into lesser
       :else
       :collect x into greater
       :finally (return
    (append (qsort-2 cmp lesser)
     (list piv)
     (qsort-2 cmp greater))))))

0 件のコメント:

コメントを投稿