HaskellとCommon Lispの勉強をコッソリ少しずつ進めている。Haskellでクイックソートが簡単に書けるのを知って嬉しい。このサイトのコードを貼り付ける。
-- 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
common lispでも同じようなやり方でクイックソートを書いてみた。
;; 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))))))
上で使われているdestructuring-bindは構造化代入というらしいが、このやり方を見つけられてよかった。common lispでも関数の入力を分解して定義本体の語彙として使える。
;; common lisp (defun fff (lst) (destructuring-bind (x . xs) lst (cons x (cons x xs))))
-- haskell fff (x:xs) = x:x:xs
上の2つは同じ。でもhaskellの方が簡潔だ。
※クイックソート2
