Haskellの練習として最も基本的なアルゴリズムであるソートを書いてみます．ソートにもいろいろありますが，今回は選択ソート，挿入ソート，マージソート，クイックソートの四つをやってみます．
選択ソートは，対象となる配列から最小値を順に抜き出して並べる方法です．Haskellの標準関数では最小値をリストから抽出して残りのリストとに分離する関数がないみたいなので，無理やり実装しています．
selectionSort :: Ord a => [a] -> [a]
selectionSort [] = []
selectionSort xs = (head (snd r)):(selectionSort (fst r ++ tail (snd r)))
where
r = extractMin xs
where
extractMin [x] = ([], [x])
extractMin (x:xs) | x < (head right) = ([], (x:left) ++ right)
| otherwise = (x:left, right)
where
left = fst (extractMin xs)
right = snd (extractMin xs)
挿入ソートは，整列済みの配列にひとつずつ要素を正しい位置(追加後も整列済みになるよう)に追加していく方法です．整列済みのリストに対して正しい位置に要素を挿入するinsertが標準関数に含まれているので，簡単に定義できます．これは，プログラミングHaskellのpp. 61-62に載っているisortそのまんまです．
insertionSort :: Ord a => [a] -> [a] insertionSort [] = [] insertionSort (x:xs) = insert x (insertionSort xs)
マージソートは，配列を二分割してそれぞれソートし結合時に順番に並べるという操作を，再帰的に行う方法です．二分割したリストに対してそれぞれ再帰的にmergeSortを行い，最後にdoMergeで結合しています．これを実装するとき，要素が一つのときの定義を忘れていて思いっきりハマりました(定義してやらないと，再帰が停止しません)．
mergeSort :: Ord a => [a] -> [a]
mergeSort [] = []
mergeSort [x] = [x]
mergeSort xs = doMerge (mergeSort (fst r)) (mergeSort (snd r))
where
r = splitAt (div (length xs) 2) xs
doMerge ys [] = ys
doMerge [] zs = zs
doMerge (y:ys) (z:zs) | y > z = z:(doMerge (y:ys) zs)
| otherwise = y:(doMerge ys (z:zs))クイックソートは，ある値を中心としてそれ以下の要素の配列とそれより大きい要素の配列をつくり，それを再帰的に繰り返すことで整列させる方法です．これも，プログラミングHaskellのpp. 8-9, 63に載っているqsortと同じです．
quickSort :: Ord a => [a] -> [a]
quickSort [] = []
quickSort (x:xs) = quickSort ys ++ [x] ++ quickSort zs
where
ys = [a | a <- xs, a <= x]
zs = [b | b <- xs, b > x]qsortが計算量もコード量も少なくていいですね．
