Arrowでクイックソート
久しぶりに書きます。この１ヶ月半ほどは、大学の試験があったり、塾の夏期講習をやったり、CPU実験が始まった(勝手に始めた)りしたのでブログの事をすっかり忘れてました。
んで、現在Haskellでコンパイラを製作なんかをしています。その為にHaskellの勉強を始めたのですが、Arrowというモジュールに出会ってどっぷりはまってしまいました。
Arrowは書きやすいのか？
Haskellと言えばやっぱりクイックソートだろうということでArrowで書いてみたんですが、こんな事になりました。あえて全部Arrowで書いているので複雑ですけれども。
qsort :: Ord a => [a] -> [a] qsort = (null >>> \x -> if x then Left else Right) &&& id >>> app >>> id ||| (head &&& ((head >>> (>) >>> partition) &&& tail >>> app >>> (qsort***qsort)) >>> \(p, (l, r)) -> l ++ [p] ++ r)
実行例
> qsort [3, 1, 5, 7, 2, 6, 8, 4, 9, 0] [0,1,2,3,4,5,6,7,8,9]
簡単に説明すると
- 1行目
- 入力を2つに複製
- 第１ライン : 入力が空リストならLeft、そうでなければRightを出力
- 第２ライン : 入力のリストをそのまま流す
- appで入力されたリストにLeftまたはRightをかぶせる
- 入力を2つに複製
- 2行目
- 空リストが流れて来たらそのまま出力(id)
- そうでなければ入力を2つに複製
- 第１ライン : リストの先頭(これがピボット)を取り出す
- 第２ライン : 入力をさらに複製
- 第１ライン : リストの先頭(pとする)を取り出し(>)、partitionに順次部分適用し関数\x -> partition (> p) x を作成
- 第２ライン : リストの先頭以外(tail)を取り出す
- 3行目
- appしてtailを２つのリストに分割
- ２つのリストそれぞれをソート(qsort**qsort)
- この時点でデータは(ピボット, (ピボットより小さい要素をソートしたリスト, ピボットより大きい...))となっているので連結すれば終了
まぁはっきり言って書きやすくはありません。最初と最後のラムダが何か汚いですし...最後のはuncurryとか使ってけば消せますが最初はどうなんでしょう。
よくArrowを使うと書きやすくなるとか言われますが、一般的な計算を行う場合には決して書きやすくなるとは言えないと思います。Arrowを使って書きやすくなる場面というのは
- 一定のデータ構造に対する流れ処理
- ちょっとした計算
くらいなのかなと思います。[追記]あくまで"関数を"Arrowとして使う場合の話です。
do記法を使えば、結局Monadと変わらないですし、記法の問題だけならばArrowを使おうって気になる人も少ないんじゃないかと思います。
そんな感じで最初はもやもやとしていたんですが、最近やっとArrowの本質が分かって来たような気がします。それについては次回書きます。
