ソート

inspired by http://d.hatena.ne.jp/yamamucho/20100110/1263082701

import Data.List

--挿入ソート
ins :: Ord a => [a] -> [a]
ins = foldl f []
  where f s x = case span (x>) s of (t,u) -> t++x:u

--選択ソート
sel :: Ord a => [a] -> [a]
sel = reverse . fst . head . (dropWith <*> iterate sel' . (,) [])
  where sel' (xs,ys) = (x:xs,delete x ys)
          where x = minimum ys

--バブルソート
bbl :: Ord a => [a] -> [a]
bbl = fst . head . (dropWith <*> iterate bbl' . (,) [])
  where 
    bbl' (ss,x:xs) = first (:ss) $ mapAccumL swap x xs
    swap x y = if x > y then (x,y) else (y,x)

dropWith (_:xs) (_:ys) = dropWith xs ys
dropWith _      ys     = ys

first f (x,y) = (f x, y)
(f <*> g) x = (f x) (g x)

infixl 4 <*>

ううむ．選択ソートって残りのリストの最小値を求めるときの「副作用」を使ってもよいのだろか？もし，そうなら

sel :: Ord a => [a] -> [a]
sel = reverse . fst . head . (dropWith <*> iterate sel' . (,) [])
  where sel' (xs,ys) = first (:ss) $ mapAccumL swap x xs
        swap x y = if x < y then (x,y) else (y,x)

これって，バブルソートじゃん．ああなるほどバブルソートってそういうもんなんだね．