人気ブログランキング | 話題のタグを見る

短い再帰関数は1行で記述しよう

Haskellのプログラムを ghci 上で作るときはたいてい1行で済ませている。ただ、再帰関数をパターンで記述するときは、base case と recursive case を別の行で記述しなくてはならないので、複数記述するために :{ コマンドを使うことになる。

ただ、不便なのはこれではプログラムを修正するのにもう一度入力し直さなくてはならなくなるということだ。一行プログラムなら上向のカーソルキーを押せば、プログラムの記述を呼び出して修正できるが、複数行のプログラムとなるとそうもいかない。

そこで、考えて、複数行で再帰関数を定義するときは { ... ; ... } によるブロックを利用することにしてみた。すると次のようにクイックソートのプログラムも難なく定義して実行することができる。

Prelude> {qsort [] = []; qsort (x:xs) = qsort (filter (<=x) xs) ++ [x] ++ qsort (filter (>x) xs)}
Prelude> qsort [4,1,5,3,2]
[1,2,3,4,5]

これだったら、プログラムの記述にミスがあっても、矢印キー一発で全てのプログラムを表示し、編集することができる。たとえば上のクイックソートを可視化したければ、呼び出したプログラムの出力が文字列になるように編集するだけでいい。

Prelude> {qsort' [] = "[]"; qsort' (x:xs) = "(" ++ qsort' (filter (<=x) xs) ++ "[" ++ show x ++ "]" ++ "(" ++ qsort' (filter (>x) xs) ++ ")"}
Prelude> qsort' [4,1,5,3,2]
"(([][1]((([][2]([])[3]([]))[4](([][5]([]))"

余談だが、簡単な再帰関数だったら、そのまま逐語的に可視化できる。それは、再帰関数の計算が、右辺に記述された自分自身の関数を、recursive case のルールで展開し(置き換え)その展開が base case にぶつかったら、右端の方から計算を実行して縮約するという計算方法になるからだ。したがって、式の計算を、文字列の処理に変換するだけで逐語的な可視化が可能になる。式の置き換えも、文字列の置き換えも抽象的な操作としては同じだからだ。

次の階乗の計算とその可視化を見ると、そのへんの仕組みがよくわかる。

Prelude> {fact 0 = 1; fact n = n * fact (n-1)}
Prelude> fact 5
120

Prelude> {fact 0 = "1"; fact n = show n ++ "*" ++ "(" ++ fact (n-1) ++ ")"}
Prelude> fact 5
"5*(4*(3*(2*(1*(1)))))"

このように、簡単な再帰関数はプロックで1行プログラムにしてしまえばいいし、再帰関数の可視化は機械的にできてしまう。


by tnomura9 | 2018-11-01 07:59 | Haskell | Comments(0)
<< 素数 クイックソートの見える化 >>