quick sort

http://d.hatena.ne.jp/uskz/20080918/p2

久しぶりにHaskellのqsortを見た。
最初は
http://d.hatena.ne.jp/Nobuhisa/20070826/1188075244#c1188200644
で同じく梶本さんに教えていただいたり。（もう1年も経つのか・・・！）
当時は全く意味不明の文字列にしか見えませんでしたが、今は集合論のわずかな知識とlist comprehensionsのわずかな知識とHaskellのわずかな知識が脳に加わったので、改めて眺めてみると理解できました。

quicksort :: [Int] -> (Int->Int->Bool) -> [Int]
quicksort [] f = []
quicksort (x:xs) f =
    quicksort [ a | a<-xs, f a x ] f
    ++ [ x ]
    ++ quicksort [ a | a<-xs, not (f a x) ] f
   
main = do
    let val = [ 3, 5, 1, 7, 4, 2, 6, 8 ]
    let q = quicksort val
    print $ q (<)
    print $ q (>)

梶本さんのC++版で

std::vector<int> v = ovn::initial_values(1,2,3,4,5,6,7,8,9,10,11,12);
std::cout << ::qsort(range_t(v));

とかやってみると凄い時間かかりそう。笑
（ソート済みの並びが一番計算量が多い）