LoginSignup
11

More than 5 years have passed since last update.

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

Last updated at Posted at 2017-03-05

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

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

まずは最も簡単な例を挙げます。breakcontinue も使わないループを、末尾再帰関数を使って書いてみましょう。ひたすら 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()

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

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

例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 にガード節がありますが、これは ifbreak に簡単に分解できて、次のように変形できます:

// 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. forforeachwhile に書き換える。
  2. while の条件があれば、 while (true) にする代わりに if (! 条件) break; を挿入する。
  3. すべての if 文に else 節を補う。
  4. while の末尾に到達する部分に continue を補う。
  5. break() にする。

おわりに

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

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
11