構造化定理によれば、分岐、反復、逐次があれば、すべてのロジックは記述できます。分岐については、Haskellの文法(分岐編)で説明しました。今日は反復について説明します。逐次に関しては、少し難しい内容ですが、QAで学ぶMonadを読んで下さい。
for 文
多くの言語では、素朴な繰り返しを実現するためには for 文や while 文を使います。for文を単純に数え上げとして使う場合、カウンターである変数 i が再代入できるとことが前提になっています。
Haskell では、変数に再代入はできません。それは、for 文がないことを意味します。どうやって、繰り返しを実現するのでしょうか？ その答えは、再帰です。
対比するための言語として JavaScript を用いることにします。まず、以下のように渡された整数の配列の要素をすべて足し合わせるプログラムを考えて下さい。
function sum0(xs) { var sum = 0; for (var i = 0; i < xs.length; i++) { sum = sum + xs[i]; } return sum; }
使ってみましょう。
sum0([-2,4,9,-1,5,-6,7]); → 16
sum0 :: [Int] -> Int sum0 [] = 0 sum0 (x:xs) = x + sum0 xs
使ってみましょう。
sum0 [-2,4,9,-1,5,-6,7] → 16
慣れてないうちは、再帰は難しく感じるかもしれませんが、そのうち簡単になります。
「ループで書けるのに再帰で書くのは馬鹿げている」という意見がありますが、それは動的型付けの言語で考えているからです。静的型付けの言語では、再帰の部分で型検査の洗礼を受け、間違いが入り込みにくくなります。僕個人は、JavaScript などで for 文を書くとき、自分のコードに自信が持てなくてとても不安になります。一方、Haskell で再帰を書くと安心できます。Haskell のコンパイラーがたくさんの間違いを探してくれますからね。
上記のコード中のプラスを丸括弧で囲んで関数として扱うように書き直してみます。
sum0 :: [Int] -> Int sum0 [] = 0 sum0 (x:xs) = (+) x (sum0 xs)
こうすれば、= の横に自分自身以外の (+) が現れていることが分かるでしょう。このような再帰は、スタックをたくさん消費してしまいます。この問題は、末尾再帰を使うと解決します。末尾再帰とは、= の横に、値か、自分自身のみが現れる形の再帰です。末尾再帰に書き換える常套手段は、引数を一つ追加することです。
sum0' :: [Int] -> Int sum0' xs = f xs 0 where f [] s = s f (y:ys) s = f ys (y + s)
使ってみると同じ答えが返ってきます。
sum0' [-2,4,9,-1,5,-6,7] → 16
break
では、break はどうやって実現するのでしょうか？
例として、配列の中に -1 を発見したら足し算を止め、それまでに計算した和を返すプログラムを書いてみます。
function sum1(xs) { var sum = 0; for (var i = 0; i < xs.length; i++) { if (xs[i] == -1) { break; } sum = sum + xs[i]; } return sum; }
使ってみましょう。
sum1([-2,4,9,-1,5,-6,7]); → 11
これを Haskell で実現すると、以下のようになります。
sum1 :: [Int] -> Int sum1 xs = f xs 0 where f [] s = s f (y:ys) s | y == -1 = s -- ここが break に相当する | otherwise = f ys (y + s)
break の目的は、それまでの和を返すことですから、和を返せばいいだけですね。
continue
continue の例もみてみましょう。以下は、負の数を排除して、0以上の数を足し合わせるコードです。
function sum2(xs) { var sum = 0; for (var i = 0; i < xs.length; i++) { if (xs[i] < 0) { continue; } sum = sum + xs[i]; } return sum; }
使ってみましょう。
sum2([-2,4,9,-1,5,-6,7]); → 25
これを Haskell で実現すると、以下のようになります。
sum2 :: [Int] -> Int sum2 xs = f xs 0 where f [] s = s f (y:ys) s | y < 0 = f ys s // ここが contiune に相当する | otherwise = f ys (y + s)
continue の目的は、足し算をせずに次の候補へ行くことですから、単に再帰すればいいですね。
節度を知る
変な話なのですが、再帰をよく理解したら、なるべく再帰を使ってはいけません。上記の例を見ると再帰が goto 文のように思えた人がいるかもしれませんが、その直観はあたっています。再帰はいろんなことが実現できるので、読み手には理解しずらいのです。
熟達した Haskeller は、以下のような力の階層を理解しています。
- 再帰
- foldr、foldl など
- filter、take など
上が力が強く、下へ行くほど力が弱くなります。力が強いと何でもできてしまうので、コードの意図が不明瞭となり、また間違いが入り込みやすくなります。力が弱いとできることは限られるのでコードの意図は明確となり、間違いが入りにくくなります。
「目的に合う一番力の弱い手段を使う」のがよいプログラムを書くための大原則です。たとえば、草を刈るのにチェーンソーは使うべきではありません。もちろん草も切れますが、大切な植木も傷つけてしまうかもしれませんから。
これまでのコードは、再帰を使わなくとも、以下のように実現できます。
sum0'' = foldr (+) 0 sum1' = sum0'' . takeWhile (/= -1) sum2' = sum0'' . filter (>=0)
再帰を使わなければ、こんなに意味が分かりやすくなるのです。なお、foldr や takeWhile 自体は再帰を使って実装されています。
