haskellに流し目

なんだかんだいいながらも関数型言語に興味があるので，ふつうのHaskellプログラミングを読んでみた．さわりだけを扱ってるっぽくするすると読める．モナドのとこは飛ばしたけど．

リストの内包表記とか数列表記，関数の部分適用とかは便利そう．

とりあえず，文法はある程度理解できたと思われるので，もう少し関連資料を読んでみる．

しかし，このクイックソートってなんかおかしくない？

qsort []     = []
qsort (x:xs) = qsort elts_lt_x ++ [x] ++ qsort elts_greq_x
                 where
                   elts_lt_x   = [y | y <- xs, y < x]
                   elts_greq_x = [y | y <- xs, y >= x]

ソート対象にもよるんだろうけど，

def quickSort( data )
  return [] if data.empty?

  x,xs = data[0], data[1..-1]
  lt_x = xs.find_all {|y| y<x }
  ge_x = xs.find_all {|y| y>=x }

  quickSort(lt_x) + [x] + quickSort(ge_x)
end

より，

def quickSort2( data )
  return [] if data.empty?

  x = data[data.size/2]
  lt_x = data.find_all {|y| y<x }
  eq_x = data.find_all {|y| y==x }
  gt_x = data.find_all {|y| y>x }

  quickSort2(lt_x) + eq_x + quickSort2(gt_x)
end

data = (1..10).map{ rand(1000) }
quick = quickSort2( data )

のほうが自然なような．

qsort [] = []
qsort s  = qsort [y|y<-s,y<x] ++ [y|y<-s,y==x] ++ qsort [y|y<-s,y>x]
             where
               x = ????

こんな感じの何かになればいいのか？