かずきのBlog@hatena

すきな言語は C# + XAML の組み合わせ。Azure Functions も好き。最近は Go 言語勉強中。日本マイクロソフトで働いていますが、ここに書いていることは個人的なメモなので会社の公式見解ではありません。

手軽なスクリプト言語としてのF# その２１「再帰とループ」

F#

さて、次は関数型言語ではループのかわりによく使われるともっぱらの噂？の再帰についてみてみようと思います。まぁ関数型言語じゃなくても再帰は一般的に使われてるけど、でかいデータを相手にしたときにスタックオーバーフロー起こすから気を付けようねって感じだと思います。
とりあえず単純にリスト内の要素の総和を求める関数を再帰を使って書いてみようと思います。

// 普通に再帰
let rec sum1 l =
    match l with
    | head::tail -> head + sum1(tail)
    | [] -> 0

// 実行してみる
let list = [1..100]
printfn "%d" <| sum1 list

パターンマッチのhead::tailは、リストに対するパターンマッチでheadに最初の要素tailに2つめ以降の要素が入ります。そして[]は空のリストにマッチするパターンです。あと、再帰呼び出しをする関数にはrecというキーワードもつけないといけない点が特徴的ですね。

やってることは簡単で、リストの最初の要素に対して残りの部分の総和を足すということを再帰的にやって、最後にリストの要素がなくなったら0を返すという一般的な再帰のパターンだと思います。実行してみると以下のような結果になります。

5050

さて、1〜100の和くらいならよかったのですが、ちょっと大きなリストの和を求めてもらうとどうなるでしょう。試してみます。数が大きいのでintではなくてint64にしました。

// 普通に再帰
let rec sum1 l =
    match l with
    | head::tail -> head + sum1(tail)
    | [] -> 0L

// 実行してみる
let list = [1L..100000L]
printfn "%d" <| sum1 list

1〜10万です、結構おおきな数字ですね。実行すると以下のようになります。

Process is terminated due to StackOverflowException.

スタックオーバーフローになってしまいました。

F#には、この問題を解決するために末尾再帰と呼ばれるものがあります。このsumの例だと再帰が最後に行くまで計算結果が確定しないのでスタックに計算途中の値を積み上げないといけないのですが、これをなくしてやろうというアプローチです。どうやるのかというと、計算の経過を関数の引数として持ちまわってやろうというアプローチになります。
ということでsumを書き換えてみます。

// 末尾再帰
let sum2 l =
    // accに計算経過いれて引数で持回る
    let rec sumLoop acc list =
        match list with
        | head::tail -> sumLoop (acc + head) tail
        | [] -> acc
    // 計算経過を0（初期値）でsumLoopを呼び出す
    sumLoop 0L l

// 実行してみる
let list = [1L..100000L]
printfn "%d" <| sum2 list

さて、実行してみましょう。

5000050000

あってるのかどうかわかりませんが、スタックオーバーフローにならずに計算結果が出ました。これは裏でF#コンパイラが空気を読んで再帰呼び出しをループに最適化してるのだと思われます。（逆コンパイルして確認したわけではないので予想です）

要は、自分で最初からループで書いても同じですね。

// ループ
let sum3 l =
    let sum = ref 0L
    for i in l do
        sum := !sum + i
    !sum

// 実行してみる
let list = [1L..100000L]
printfn "%d" <| sum3 list

ただ、ループを書くと副作用のある変数を作ったりあまり関数型チックとは言えないのと、再帰的に扱えるものは再帰で書いたほうがすっきりするので、末尾再起になるように心がけて書いていこうと思った今日この頃でした。


過去記事