Insersion Sort

Haskell 30分プログラム

30分プログラム、その715。2009-11-30 - Haskellで遊ぶよ - haskellにインスパイアされました。
書いてから上記のページを見てみたんけど、http://haskell.org/ghc/docs/latest/html/libraries/base-4.2.0.0/Data-List.htmlのinsertやinsertByがあったのか。こっちを使えばよかったなぁ。
あと、昔の記事をあさったたら、2年ほど前に書いたinsersion sortがでてきました(ソートをいろいろ - みずぴー日記)。こっちは、foldrじゃなくてfoldlを使ってますね。foldrのほうが遅延評価と相性がいいとか、なんとか。

使い方

*Main> isort [3,4,5,3,2,1,4]
[1,2,3,3,4,4,5]

ソースコード

insert :: Ord a => a -> [a] -> [a]
isort  :: Ord a => [a] -> [a]

insert x [] = [x]
insert x yss@(y:ys) = if x < y then
                          x:yss
                      else
                          y:insert x ys

isort = foldr insert []

参考