前にブログに貼り付けたクイックソートのコードをほんの少しだけ読みやすくしたい。内包表記の部分を書き換える。まずは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 (2*) [1..10]
[2,4,6,8,10,12,14,16,18,20]
> [2*x | x <- [1..10]] == map (2*) [1..10]
True
> [2*x | x <- [1..10], odd x]
[2,6,10,14,18]
> 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系関数を適用することによって内包を表現する。