クイックソート2

　前にブログに貼り付けたクイックソートのコードをほんの少しだけ読みやすくしたい。内包表記の部分を書き換える。まずはhaskell。

-- 前
quicksort :: (Ord a) => [a] -> [a]  
quicksort [] = []  
quicksort (x:xs) =   
    let smallerSorted = quicksort [a | a <- xs, a <= x]  
        biggerSorted = quicksort [a | a <- xs, a > x]  
    in  smallerSorted ++ [x] ++ biggerSorted
-- 後
quicksort :: (Ord a) => [a] -> [a]    
quicksort [] = []    
quicksort (x:xs) =     
    let smallerSorted = quicksort (filter (<= x) xs)  
        biggerSorted = quicksort (filter (> x) xs)   
    in  smallerSorted ++ [x] ++ biggerSorted

　filterを使った。次はcommon lisp。

;; 前
(defun quicksort (lst)
  (if (null lst) ()
    (destructuring-bind (x . xs) lst
      (let ((smaller (loop for i in xs when (< i x) collect i))
            (bigger (loop for i in xs when (>= i x) collect i)))
        (concatenate 'list 
                     (quicksort smaller)
                     (list x)
                     (quicksort bigger))))))
;; 後
(defun quicksort (lst)
  (if (null lst) ()
    (destructuring-bind (x . xs) lst
      (let ((smaller (remove-if-not (lambda (i) (< i x)) xs))
            (bigger (remove-if-not (lambda (i) (>= i x)) xs)))
        (concatenate 'list 
                     (quicksort smaller)
                     (list x)
                     (quicksort bigger))))))

　loopをやめてfilter系の関数remove-if-notを使用した。common lispでの方が書き換えの効果は大きい気がする。

---

　filter系の関数とmap系の関数を組み合わせて使えば内包表記を書き換えられるし、その逆もできるのだろう。haskellのghciを使ってみる。

-- 内包で生成
> [2*x | x <- [1..10]]
[2,4,6,8,10,12,14,16,18,20]
-- mapで生成
> map (2*) [1..10]
[2,4,6,8,10,12,14,16,18,20]
-- 上の２つは同じ
> [2*x | x <- [1..10]] == map (2*) [1..10]
True

-- xはodd(奇数)である、という条件をつける
> [2*x | x <- [1..10], odd x]
[2,6,10,14,18]
-- リスト[1..10]にfilterをかけてからmapを適用する
> map (2*) (filter odd [1..10])
[2,6,10,14,18]
-- 上の２つは同じ
> [2*x | x <- [1..10], odd x] == map (2*) (filter odd [1..10])
True

引数として放り込むリストにfilter系関数で条件をつけて、それにmap系関数を適用することによって内包を表現する。