Edited at

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

More than 1 year has passed since last update.

手続き型言語を使う人に「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つの手かもしれません。