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] あっけないほど短い。しかしそれだけでなく、クイックソートのアルゴリズムがよく分かるプログラムになっている。 1) 空リストは並べ替えても空リストである。 再帰的プログラムでは、停止の条件を決めておかないと、永遠に再帰状態が終わらなくなる。 2) リストの左端の要素を取り出す。 2行目の (x:xs) というパターンは、リストの先頭の要素を x に、それ以降のリストを xs にバインドすることを示す。つまり、左端の要素を取り出すということ。 3) x を取り出した残りの要素のリスト xs から、 x より小さい要素を集めて、elts_lt_x (elements less than x) という集合を作る。 [y | y <- xs, y < x] はリストの内包的な定義だが、集合の記法とそっくりに書くことができる。 4) x を取り出した残りの要素のリスト xs から、 x 以上の要素を集めて、elts_greq_x (elements greater than or equal x) という集合を作る。 5) x を一つ入れたリスト [x] の左に、elts_lt_x をソートしたものを連結し、[x] の右に elts_greq_x をソートしたものを連結する。 最初の1ステップでは、elts_it_x, [x], elts_greq_x という集合は確定するが、elts_lt_x や elts_greq_x はまだソートされていない。そこで qsort elts_it_x と qsort elts_greq_x が実行されるので [x] の両側の数列についても再帰的に作業が行われていく。こういうアルゴリズムをそのまま記述しただけのようなプログラムが実際に動くというのが面白い。以前から、考えることを補助してくれるプログラム言語はないだろうかと思っていたが、現在のところ、Haskell がそれに一番近いような気がする。まだ慣れていないのでわからないが、何かアイディアを思いついたら先ず Haskell でプログラムして、それから、そのアイディアの足りないところをチェックしていくというような使い方ができるようになったら素敵だ。 追記 qsort プログラム別解 Prelude> let qsort [] = []; qsort (x:xs) = qsort (filter (<x) xs) ++ [x] ++ qsort (filter (>=x) xs) Prelude> qsort [2,9,7,3] [2,3,7,9] Prelude> qsort "hello" "ehllo"
by tnomura9
| 2009-08-09 05:22
| Haskell
|
Comments(0)
|
カテゴリ
新型コロナウイルス 主インデックス Haskell 記事リスト 圏論記事リスト 考えるということのリスト 考えるということ ラッセルのパラドックス Haskell Prelude Ocaml ボーカロイド 圏論 jQuery デモ HTML Python ツールボックス XAMPP Ruby ubuntu WordPress 脳の話 話のネタ リンク 幸福論 キリスト教 心の話 メモ 電子カルテ Dojo JavaScript C# NetWalker ed と sed HTML Raspberry Pi C 言語 命題論理 以前の記事
最新のトラックバック
最新のコメント
ファン
記事ランキング
ブログジャンル
画像一覧
|
ファン申請 |
||