「プログラミング Haskell」 読書メモ 6.2リストに対する再帰

プログラミング Haskell 6章 再帰関数 6.2リストに対する再帰

小さい順に並んでいるリストを先頭より比較し、リストの要素の値が挿入しようとする値と同じか大きくなったところに挿入される。

-- 挿入ソート
insert :: Ord a => a -> [a] -> [a]

insert x [] = [x]
insert x (y:ys) | x <= y    = x:y:ys
                | otherwise = y:insert x ys

isort :: Ord a => [a] -> [a]
isort []     = []
isort (x:xs) = insert x $ isort xs

 *Main> insert 'c' "abcd"
 "abccd"

 *Main> isort [23,12,4,78,15,9]
 [4,9,12,15,23,78]
 *Main> isort ["hello","world","abc"]
 ["abc","hello","world"]

リストの中味は Ord クラスのインスタンスなら何でも良い。