break可能なループを書こう - 関数型プログラミングのテクニック

Qiita

手続き型言語を使う人に「F# のループ (for/while) は break できない」というと驚かれるかもしれません。筆者は驚きました。途中で終了する可能性のあるループを書けなくて困りそうですが、その心配は不要です。F# では 末尾再帰関数 を使って、break や continue のあるループと同じことができるからです。

例1: 無条件の無限ループ

まずは最も簡単な例を挙げます。break も continue も使わないループを、末尾再帰関数を使って書いてみましょう。ひたすら yes を出力するだけの、通称 yes コマンドです。C# だとこうですね。

public void YesAll()
{
    while (true)
    {
        Console.WriteLine("yes");
    }
}

これなら F# の while でも同様に書けますが、練習のため末尾再帰で書いてみましょう。

let yesAll () =
    let rec loop () =
        Console.WriteLine("yes")
        loop ()
    loop ()

コードの説明をします。冒頭の let yesAll () = ... は関数の定義で、残りの部分がその本体です。let rec loop () = ... も関数の定義ですが (関数の中に関数！)、rec キーワードがついているので loop 関数は再帰的(recursive)です (再帰的な関数については後述)。

F# は字下げに依存した構文を採用しています。loop 関数の定義は、字下げが let と同じ深さに戻ったところで終わります。すなわち、loop の本体は2行からなり、字下げの減っている最後の loop () は含まれません。

loop 関数の定義の後ろにある loop () は、事実上 yesAll が最初に実行する式ですが、単に loop 関数を起動するだけです。

再帰についてもう少し解説します。loop の本体は「yes を出力する」式と「loop を起動する」式の2つからなります。loop の中で loop を起動すると、また「yes を出力する」と「loop を起動する」を実行することになります。すなわち、

loop を起動する
= yes を出力して、次に loop を起動する
= yes を出力して、次に yes を出力して、次に loop を起動する
= yes を出力して、次に yes を出力して、次に yes を出力して、次に loop を起動する
= ……

という計算になります。無限ループですね。実際、これは C# で書いたものとほぼ同じループにコンパイルされるはずです。

機械的翻訳

C# の視点から loop 関数を解釈する手段を紹介します。まず C# のコードのうち、while の「末尾」に到達する部分に continue を挿入します。

// C#

public void YesAll()
{
    while (true)
    {
        Console.WriteLine("yes"); // body
        continue; // 追加
    }
}

そして、一定の規則で F# のコードに変換します。

// F#

let yesAll () =
    let rec loop () =            // while (true) {
        Console.WriteLine("yes") //   body
        loop ()                  //   continue;
    loop ()                      // }

つまり、 while (true) { ... } を

    let rec loop =
        ...
    loop()

に置き換え、ループの本体のうち continue を loop () に置き換えました。

こうして簡単に末尾再帰バージョンを手に入れることができます。

例2: 停止する無限ループ

先ほどの例で基本的な考え方を会得したので、break を使うループの例を見ていきましょう。

以下の関数は、標準入力から行を読み込むたびに「叫ぶ」(大文字に変換して出力する)ものです。入力を読み切ったら自動的に終了することにします。

// C#

private void ScreamLine(string line)
{
    Console.WriteLine(line.ToUpper() + "!");
}

public void Scream()
{
    while (true)
    {
        // 標準入力から1行を取得する。
        // 入力の終端に到達していたら、null が返る。
        var line = Console.ReadLine();
        if (line == null) break;

        ScreamLine(line);
    }
}

これを少しだけ変形します。if 文には常に else をつけ、末尾に到達する部分に continue を挿入します。

// C#

public void Run()
{
    while (true)
    {
        var line = Console.ReadLine();
        if (line == null)
        {
            break;
        }
        else
        {
            ScreamLine(line);
            continue;
        }
    }
}

そして、前述の変換に加えて break を () に置き換えると完成です：

// F#

let screamLine (line: string) =
    Console.WriteLine(line.ToUpper() + "!")

let scream () =
    let rec loop () =                   // while (true) {
        let line = Console.ReadLine()   //   var line = ...;
        if line = null then             //   if (line == null) {
            ()                          //     break;
        else                            //   } else {
            scream line                 //     ...;
            loop ()                     //     continue;
                                        //   }
    loop ()                             // }

() と break が対応することのイメージが分からないと思いますが、直接的な対応はないので、 scream () の挙動を説明します。

この関数を scream () のように起動すると、先程の yesAll () と同じく loop () が開始します。loop の返り値は、読み取った行が null なら (= 入力が終了したら) () (ユニットという名前の定数) で、そうでなければ else 節の値になります。else 節では、入力を叫んだあとループをやり直しますが、yes コマンドとは違っていつかは入力が終わり () が返ってきます。結局、標準入出力の副作用を除けば

scream ()
= loop ()
= ...
= loop ()
= ()

となります。() という「ループを伸ばさない式」のおかげで loop の連鎖が切れて、つまりループが終了して (break して) いますね。

C# ではループを続けるのに continue は書かなくていい代わりに、終わらせるときに break を書きます。一方この末尾再帰関数のやりかたでは、ループを終わらせるのに break は書かなくていい代わりに、続けるときに loop () を書くのです。

例3: 有限回のループ

前の2つの例の loop 関数は、引数として () を受け取りましたが、実際は任意の引数が使えます。ループの「状態」を引数で持ち運ぶのはよくあることです。

最後の例は、リストの各要素を1行ずつ表示していくループです。 F# だと for で書けますが、練習のため末尾再帰関数で書きます。

public void PrintList<X>(IReadOnlyList<X> list)
{
    var index = 0;
    while (index < list.Count)
    {
        Console.WriteLine("{0}", list[index]);
        index++;
    }
}

今回は while にガード節がありますが、これは if と break に簡単に分解できて、次のように変形できます：

// C#

public void PrintList<X>(IReadOnlyList<X> list)
{
    var index = 0;
    while (true)
    {
        if (index < list.Count) // 条件節
        {
            Console.WriteLine("{0}", list[index]);
            index++;
            continue; // 追加
        }
        else
        {
            break; // 条件不成立 (index >= list.Count) なら終了。
        }
    }
}

// F#

let printList (list: IReadOnlyList<_>) =
    let rec loop index =                           // while (true) {
        if index < list.Count then                 //    if (...) {
            Console.WriteLine("{0}", list.[index]) //      ...;
            loop (index + 1)                       //      continue;
        else                                       //    } else {
            ()                                     //      break;
                                                   //    }
    loop 0                                         // }

loop 関数の実行を簡単に追ってみましょう。list を長さ 3 のリストとすると、

loop 0
= 0 < 3 なら、出力して loop 1
= loop 1
= 1 < 3 なら、出力して loop 2
= loop 2
= 2 < 3 なら、出力して loop 3
= loop 3
= 3 < 3 なら、出力して loop 4
= (なにもしない)
= ()

となります。

まとめ: 変換規則

1. for や foreach は while に書き換える。
2. while の条件があれば、 while (true) にする代わりに if (! 条件) break; を挿入する。
3. すべての if 文に else 節を補う。
4. while の末尾に到達する部分に continue を補う。
5. break を () にする。

おわりに

本稿では、C# のループを比較的単純に末尾再帰関数に変換できることを紹介しました。実際のところ、再帰は再帰として理解したほうがいいと思いますが、こういう小手先のテクニックを用いて理解を深めていくのも1つの手かもしれません。

関連記事

• CombineLatestのリアクティブグリッチ
• [F#][小ネタ] Unreachableアクティブパターン
• リンクのための型エイリアス
• 可視性を使ってnever型もどきを作る
• 相互再帰関数の型推論で問題になったケース