関数型な書き方が得意な言語を比較。目に付いたモノを一通り見ただけの自分メモです。。

Erlang

1
2
3

 qsort([]) -> [];
 qsort([Pivot|Rest]) ->
     qsort([ X || X <- Rest, X < Pivot]) ++ [Pivot] ++ qsort([ Y || Y <- Rest, Y >= Pivot]).

from http://ja.wikipedia.org/wiki/Erlang#.E9.96.A2.E6.95.B0.E5.9E.8B.E8.A8.80.E8.AA.9E

Haskell

1
2

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

from http://d.hatena.ne.jp/salmonsnare/20090414/1239690094

OCaml

1
2
3
4
5

let rec quicksort = function
    [] -> []     (* base case *)
  | hd::tl ->
      let (lt, gt) = List.partition (fun i -> i < hd) tl in
        (quicksort lt)@[hd]@(quicksort gt);;

from http://www.i.kyushu-u.ac.jp/~bannai/ocaml-intro/first_use.html

Scala

1
2
3
4
5

 def qsort(list: List[Int]): List[Int] = 
   list match {
     case Nil => Nil
     case pivot::tail => qsort(tail.filter(_ < pivot)) :: pivot :: qsort(tail.filter(_ >= pivot))
   }

from http://en.wikipedia.org/wiki/Scala_%28programming_language%29#Functional_programming

所感

  • 一つ読めればみんな読める（僕の場合まずErlangを一通りやったんだけど、他のもまあ、同じ考えかなって）
  • 関数型だとQuick Sortって直感的な気がする
  • リスト内包表現があると短い
  • 再帰、パターンマッチング、carとcdr的なもの
  • というか4つともシンタックスハイライトが効いてて驚愕

おまけ

  • Rubyの場合

どうとでも書けるけど、こう書けますよね。

1
2
3
4
5

def quick_sort(*args)
  return [] if args.empty?
  pivot = args.pop
  quick_sort(*args.select{|v| v < pivot}) + [pivot] + quick_sort(*args.select{|v| v >= pivot})
end

「Array#pop」という明らかに副作用のあるメソッドを使った方が短くなる。。とはいえ、大体同じ考え方で書けてしまいます。

追記。もっとひどくて短い書き方を思いついた。。

1
2
3
4

def quick_sort(*args)
  return [] if (pivot, *tail = args).empty?
  quick_sort(*tail.select{|v| v < pivot}) + [pivot] + quick_sort(*tail.select{|v| v >= pivot})
end