再帰で考える

F# C#

再帰は関数型言語を構成する重要な部品の一つです*1。
しかし、手続型言語に慣れたプログラマにとって、再帰で考えるというのは難しいものがあります。
このエントリは、そういうプログラマが再帰で考えることができるようになるために書きました。
言語としては、F# と C# を使っています (推奨は F#。C# の例は実用性が無いに等しい) が、Java プログラマでもある程度読めるでしょう。
前提条件として、これらの言語の文法は知っているものとします。
特に、C# で言う Func デリゲートを多用します。


すごい長いので、時間があるときに一気にどうぞ。
再帰以外の話もちょろちょろと出てきます。

再帰の重要性

いきなりですが、再帰はあくまで最後の手段です。
普通は再帰をカプセル化した関数を使うことになります。


通常使わないのであれば、再帰を学ぶことに意味はないのでしょうか？
いいえ、それでも再帰を学ぶことに意味はあります。
最初にも書いたように、再帰と言うのは関数型言語において一番基本的な部品の一つなのです。
再帰が使えないというのは、極端なことを言ってしまえば、手続型言語でループを知らないのと同じようなことなのです。

再帰へのアプローチ

数をこなすことで感覚を掴んでもらうのがこのエントリのアプローチです。
構成は、

  1. 具体的な例を実装
  2. ひとつ前の練習問題の答
  3. 練習問題

の繰り返しとなっています。
具体的な例の実装を読み、練習問題を解いていってもらいます。


一つ注意ですが、ここで紹介するのはあくまで書き方であって、読み方ではありません。
まぁここで紹介した例を全部自分で実際にやれば、大抵の再帰は読めるようになるでしょう。

ルール

再帰を学ぶために必要なルールを以下に示します。

  1. while / for / foreach は使ってはいけない
  2. 変数への再代入をしてはいけない
  3. if には 必ず対応する else を書くこと (条件演算子が使いたい人はそちらを使っても可)

もちろん、F# の List/Seq/Array モジュールの関数使うだとか、LINQ 使うだとかは駄目です。


あと、各言語での表記を統一するため、「〜の列」という表現をしますが、これは各言語では次のように置き換えて読んでください。

F#
リスト
C#
配列

それでは始めましょう！

sum

int の列の各値を合計した int の値を返す関数を作ります。
例えば、「1, 2, 3, 4, 5」という列を sum に与えた場合、15 と返ってくるような関数です。
大枠はこうなります。

(* F# *)
(* int list -> int *)
let rec sum xs =
  ...

// C#
public static int Sum(int[] xs)
{
    ...
}

まずはじめに、一番簡単な場合を考えましょう。
一番簡単な場合は、空の列を渡した場合でしょう。この時は 0 を返すことにします。
これが再帰の終了条件となります。

let rec sum xs =
  match xs with
  | [] -> 0 (* リストが空の場合は0を返し、これ以上再帰しない *)
  | ...

public static int Sum(int[] xs)
{
    // ルール3によりelseは絶対に書く
    if (xs.Length == 0)
        return 0; // 配列が空の場合は0を返し、これ以上は再帰しない
    else
    {
        ...
    }
}

次に、それ以外の場合 (つまり列が空でない場合) を考えます。
まぁ再帰関数なので再帰を使うわけです。再帰関数では一番簡単な場合を再帰の終了条件にして、それ以外の場合を再帰にするのが定石です。
しかし、何も考えずに再帰を書いてしまうと、いつまでたっても終了条件に辿りつけない、無限ループになってしまう可能性があります。
これを防ぐための指針として、「再帰の終了判定に使う入力が毎回減少するかどうか」を気を付けましょう。
入力が毎回減っていけば、必ずいつかは終了条件に辿りつくはずですよね。
では入力の減少とは何でしょうか？
目的としては何とかして終了条件に持っていきたいわけですので、それを目指しましょう。
今回の例では、列の長さを再帰ごとに一つずつ短くしていけば、いずれ終了条件にぶつかり、再帰が終了します。


F# では、パターンマッチによってリストを先頭要素とそれ以降の要素に分割できますからそれを使いますが、C# の配列ではそういうことはできません。
そこで、これ以降でも使う便利関数を定義しておきます。

// 引数xsを、先頭の要素とそれ以降の要素のタプルとして返す
static Tuple<T, T[]> HeadTail<T>(T[] xs)
{
    Func<T[], T[]> tail = a =>
    {
        T[] res = new T[a.Length - 1];
        Array.Copy(a, 1, res, 0, res.Length);
        return res;
    }
    return Tuple.Create(xs[0], tail(xs));
}

本題に戻ります。
今回の例では、一つ短くした列を再帰呼び出しの時の引数として渡せば、いつかは列が空になって再帰が終わります。
これをコードに落とすと、

let rec sum xs =
  match xs with
  | [] -> 0
  | y::ys -> ... (sum ys) (* ysはxsの先頭要素1つ分毎回短くなっていく *)

public static int Sum(int[] xs)
{
    if (xs.Length == 0)
        return 0;
    else
    {
        // y_ys.Item1はF#のコードのyに、y_ys.Item2はF#のコードのysに対応
        var y_ys = HeadTail(xs); 
        return ... Sum(y_ys.Item2);
    }
}

となります。
ここで、(sum ys)、もしくは Sum(y_ys.Item2) の意味を考えてみます。
これは、sum が完成すれば、入力である xs の先頭要素以外の要素の合計が返ってくるはずです。


例えば、「1, 2, 3, 4, 5」という列の合計を考えると、最初の呼び出しでは y に 1、ys に「2, 3, 4, 5」が入ります。
ここで sum が完成していると仮定すると、(sum ys) の結果は 2〜5 の合計、つまり 14 です。
それと先頭要素である 1 を使って、入力である xs のすべての要素の合計を求めたいわけですが、どうすればいいでしょうか？
そうですね、足すだけです。

let rec sum xs =
  match xs with
  | [] -> 0
  | y::ys -> y + (sum ys)

public static int Sum(int[] xs)
{
    if (xs.Length == 0)
        return 0;
    else
    {
        // y_ys.Item1はF#のコードのyに、y_ys.Item2はF#のコードのysに対応
        var y_ys = HeadTail(xs); 
        return y_ys.Item1 + Sum(y_ys.Item2);
    }
}

これで完成です。
どうでしょうか？
簡単だ、と思った方は次へお進みください。
狐につままれたようだ、と感じた方はここでたくさんの言葉を並べて説明するよりも、数をこなして感覚を身に付けるのが近道だと思います。次へお進みください。

練習問題 1

任意の型の列の長さを返す length 関数を作ってください。

(* 'a list -> int *)
let rec length xs =
  ...

// 当たり前だけど、xs.Lengthとかそういうのは求めてないです
public static int Length<T>(T[] xs)
{
    ...
}

ヒントは、「最後のステップ以外は sum とほとんど同じになる」です。
sum で追った手順をそのまま辿っていくとよいでしょう。


もう一つヒントを出しましょう。
「列の長さと再帰の回数の関係」を考えてみてください。
例えば、「5, 8, 2, 3」という列の長さと、再帰の回数を図にするなどして数えてみてください。
最後の手順で再帰部分が増えたりはしませんので、未完成のコードでも各呼び出しを表にするなどして再帰の回数が追えます。

max

int の列の最大値を返す関数を作ります。
例えば、「5, 8, 2, 3」という列を max に与えた場合、8 と返ってくるような関数です。
大枠はこうなります。

(* int list -> int *)
let rec max xs =
  ...

public static int Max(int[] xs)
{
    ...
}

sum や length の時同様に、まずは一番簡単な例を考えます。
今回は、要素が 1 つの時でしょう。この場合にはその要素を返せばいいですよね。
これが今回の再帰の終了条件となります。

let rec max xs =
  match xs with
  | [x] -> x
  | x::xs -> ... (max xs)  (* 引数と同じ名前を使っているが、maxに渡されるのは引数ではなく、分解した方のxs(シャドウイング) *)

public static int Max(int[] xs)
{
    if (xs.Length == 1)
        return xs[0];
    else
    {
        var x_xs = HeadTail(xs); 
        return ... Max(x_xs.Item2);
    }
}

今回もまた、減少していくのは列の長さですので、分解と再帰呼び出しの部分も埋めました。
(max xs)、もしくは Max(x_xs.Item2) によって返されるのは先頭要素以外の中での最大値ですので、それと先頭要素を比べて大きい方を返せばいいでしょう。

let rec max xs =
  match xs with
  | [x] -> x
  | x::xs ->
      let ret = max xs
      if ret < x then x
                 else ret

public static int Max(int[] xs)
{
    if (xs.Length == 1)
        return xs[0];
    else
    {
        var x_xs = HeadTail(xs); 
        var ret = Max(x_xs.Item2);
        return ret < x ? x
                       : ret;
    }
}

ここで、F# を使っていた人は、

    match xs with
  --------^^

c:\stdin(52,9): warning FS0025: この式のパターン一致が不完全です たとえば、値 '[]' はパターンに含まれないケースを示す可能性があります。

というような警告が出たはずです。
これは、match 式がパターンを網羅していないことを指摘しています。
今まで考えてきませんでしたが、この関数に空の列を与えた場合、C# 版の場合 HeadTail の res を作る部分で例外で落ち、F# 版の場合は match 式で MatchFailureException によって落ちます。
それをコンパイラが警告として知らせてくれたのです。
これを解決するためには、関数のシグネチャを変更して戻り値の型を option で包むか、空の時に int の最小値を返すようにしておくことが考えられます。
後者の場合、列の中に int の最小値があったのか、単に列が空だったのかの判断が付かないために、別の制限が付いてしまいます。
今回はそこを突っ込んでも仕方ないので、このままにしておきましょう。


他にも、F# の REPL で試していた人は int list -> int にならなかったことにも気づいたでしょう。
REPL は、次の応答を返したはずです。

val max : 'a list -> 'a when 'a : comparison

これは、比較可能な型を要素に持つリストであればどんなリストでもいい、ということを言っています。
max ではリストの要素に対しては < 演算子による比較しかしていません。
そのため、リストの要素が比較可能な型でさえあればここで定義した max 関数に渡せるのです。
int のリストしか許したくない！という場合には、型注釈をつけることで対応します。

let rec max (xs: int list) =
  match xs with
  | [x] -> x
  | x::xs ->
      let ret = max xs
      if ret < x then x
                 else ret

逆に C# 版を IComparable に対応させる場合、< 演算子を直接使うことができないため、割と面倒なことになります。

練習問題 1 の答

列の要素数を返す length 関数を書く問題でした。

let rec length xs =
  match xs with
  | [] -> 0
  | _::ys -> 1 + (length ys)

public static int Length<T>(T[] xs)
{
    if (xs.Length == 0)
        return 0;
    else
    {
        var y_ys = HeadTail(xs); 
        return 1 + Length(y_ys.Item2);
    }
}

sum では先頭要素とそれ以降の要素の合計を足していましたが、length では要素の内容自体はどうでもよく、長さだけが知りたかったので再帰ごとに 1 を足していくだけです。

練習問題 2

列の最小値を返す min 関数を作ってください。
ヒントはなしです。コピペせずに (あとできれば max 関数を見ずに) 作ってください。

forall

列の全要素が条件を満たす場合は true を、一つでも条件を満たさない要素がある場合は false を返す関数を作ります。
例えば、「2, 4, 6, 8」という列と「値が偶数かどうかを返す関数」を forall に与えた場合、true が返ってきますが、「2, 4, 5, 6」という列と「値が偶数かどうかを返す関数」という関数の場合、false が返ってきます。
大枠はこうです。

(* ('a -> bool) -> 'a list -> bool *)
let rec forall pred xs =
  ...

public static bool Forall<T>(T[] xs, Func<T, bool> pred)
{
    ...
}

F# と C# で引数の順番が異なる点に注目してください。
今までは引数が一つしかありませんでしたので、順番は意識しませんでしたが、今回は 2 つあるので違いが表れてきました。
C# では、対象となるオブジェクトを引数の先頭に持ってくるのが普通です*2。
それに対して、F# ではそういう引数を一番最後に持ってきています。
これには、

  • 部分適用を考慮して、固定化できそうな引数をより前に持ってくる
  • 前方パイプライン演算子の使用を考慮して、操作の対象となる引数を一番最後に持ってくる
  • パターンマッチによる分解の対象が最後にあると、function 式が使えるため、不要な変数を減らせる

などの理由があります。
とりあえず、理由があって順番が違っているんだな、くらいに思っておいてください。


今回は空の列が渡された場合を考えてみます。
「すべての要素が条件を満たす」というのは、言い換えれば「条件を満たさない要素が無い」となります。
空の列が渡された場合に条件を満たさない要素はもちろんありませんので、true を返せばよいでしょう。

let rec forall pred = function
| [] -> true
| x::xs -> ... (xs |> forall pred)

public static bool Forall<T>(T[] xs, Func<T, bool> pred)
{
    if (xs.Length == 0)
        return true;
    else
    {
        var x_xs = HeadTail(xs); 
        return ... Forall(x_xs.Item2, pred);
    }
}

今回も一気にほぼ完成系まで書き上げました。
あとは先頭要素と、それ以降の要素を forall に渡した結果とをどうすれば望む結果が得られるか考えるだけです。
表にしてみましょう。

先頭要素をpredに渡した結果 先頭以降の要素を Forall に渡した結果 望む結果
true true true
true false false
false true false
false false false

論理積 (AND) ですね。&& を使えば良さそうです。

let rec forall pred = function
| [] -> true
| x::xs -> (pred x) && (xs |> forall pred)

public static bool Forall<T>(T[] xs, Func<T, bool> pred)
{
    if (xs.Length == 0)
        return true;
    else
    {
        var x_xs = HeadTail(xs); 
        return pred(x_xs.Item1) && Forall(x_xs.Item2, pred);
    }
}

さて、F# 版がとても短くなっていることに気付いたでしょうか。
さっきちょろっと紹介した function 式というものを使っています。
この function 式と言うのは、match 式を伴う一引数関数の無名関数を作るためのシンタックスシュガーです。
・・・ってなんのこっちゃ。
とりあえず、以下の 3 つのコードは同じ意味です。

let rec sum xs =
  match xs with
  | [] -> 0
  | x::xs -> x + (sum xs)

let rec sum = fun xs ->
  match xs with
  | [] -> 0
  | x::xs -> x + (sum xs)

let rec sum = function
| [] -> 0
| x::xs -> x + (sum xs)

以下の 3 つのコードも同じ意味です。

let rec forall pred xs =
  match xs with
  | [] -> true
  | x::xs -> 

let rec forall pred = fun xs ->
  match xs with
  | [] -> true
  | x::xs -> 

let rec forall pred = function
| [] -> true
| x::xs -> (pred x) && (xs |> forall pred)

function 式を使うと、宣言部分からは引数が一つ消えたように見え、関数内部でその消えた引数を直接使うことはできなくなるかわりに、その引数に対して直接 match 式のようなパターンマッチを適用できるため短く書ける、くらいに思っておいてください。
function キーワードを改行する派もいるんですが、インデントを浅く保てるのと、「引数が見た目上一つ消えてますよ」というのが分かりやすいため、= と同じ行に function を書く派です。
ちなみに、function を = とは別の行に書く派は、予想では「改行しないと特別な構文じゃないのに特別な構文に見えそうだから改行する」とかがその理由でしょうか。
とりあえず、「特別な構文じゃないんだ、へぇー」と思ってもらえればいいです (fun が使えるところでは function も使えます)。

練習問題 2 の答

列の最小値を返す関数 min を書く問題でした。

let rec min xs =
  match xs with
  | [x] -> x
  | x::xs ->
      let ret = min xs
      if x < ret then x
                 else ret

public static int Min(int[] xs)
{
    if (xs.Length == 1)
        return xs[0];
    else
    {
        var x_xs = HeadTail(xs); 
        var ret = Min(x_xs.Item2);
        return x < ret ? x
                       : ret;
    }
}

これは演算子を変えるだけなので簡単だったと思います。

練習問題 3

列の全要素が条件を満たす場合は true を、一つでも条件を満たさない要素がある場合は false を返す関数を作ります。
列の要素のうち一つでも条件を満たす要素があれば true を、そうでない場合は false を返す関数 exists を作ってください。
空の列の場合に何を返せばいいかも自分で考えてください。

find

条件が true を返す一番初めの要素を返す関数を作ります。
要素が見つからなかった場合は null を返すことにしましょう。


要素が見つからなかった場合と言うのは、これ以上探す対象が無い、ということです。
つまり、終了条件は空の列かどうか、で良さそうです。

(* ('a -> bool) -> 'a list -> 'a when 'a : null *)
let rec find pred = function
| [] -> null
| x::xs -> ... find pred xs

public static T Find<T>(T[] xs, Func<T, bool> pred) when T : class
{
    if (xs.Length == 0)
        return null;
    else
    {
        var x_xs = HeadTail(xs); 
        return ... Find(x_xs.Item2, pred);
    }
}

あとは、先頭要素が条件を満たす場合は (再帰を打ち切って) それをそのまま返せばいいだけなので、

(* ('a -> bool) -> 'a list -> 'a when 'a : null *)
let rec find pred = function
| [] -> null
| x::xs -> if pred x then x
                     else find pred xs

public static T Find<T>(T[] xs, Func<T, bool> pred) when T : class
{
    if (xs.Length == 0)
        return null;
    else
    {
        var x_xs = HeadTail(xs); 
        return pred(x_xs.Item1) ? x_xs.Item1
                                : Find(x_xs.Item2, pred);
    }
}

となります。

練習問題 3 の答

forall が終了条件の場合に true を返し、以降各要素を pred に渡した結果の論理積だったのに対し、exists はそれが false と論理和になっただけです。

let rec exists pred = function
| [] -> false
| x::xs -> (pred x) || (xs |> exists pred)

public static bool Exists<T>(T[] xs, Func<T, bool> pred)
{
    if (xs.Length == 0)
        return false;
    else
    {
        var x_xs = HeadTail(xs); 
        return pred(x_xs.Item1) || Exists(x_xs.Item2, pred);
    }
}
ちょっと休憩

ここまでで、リスト (もしくは配列) 上の再帰にはだいぶ慣れてきたんじゃないでしょうか？
パターンも見えてきたかと思います。
要は、

  • 再帰の終了条件と、その時に返す値
  • 再帰部分と先頭要素 (と引数) から望む結果を生み出す

の形に問題を落とし込むことさえできればいいのです。
リスト上の操作と言うのは、大抵はこの形に落とし込めるので、再帰で書くことができます。


これらの関数をループで書こうと思った場合を改めて考えてみましょう。

  • ループの終了条件を考える
  • ループの一回一回の処理を考える

これは、先ほど挙げた 2 つの点と対応しています。
この中で、ループの終了条件というのは基本的には「カーソルが最後まで進んだら」でした。
例えばループカウンタを伴う for 文の場合はループカウンタである i が配列の長さと同じになったら、です。
また、foreach 文を使う場合はイテレータが最後まで行ったら、です。


このように、ループの基本的な形では終了条件は意識することはありませんし、その時に何かを返すことは強制されていません。
本体が空のループだったら何も考えずに書くことができる、ということです。


それに対して、再帰は for や foreach のように言語組み込みの構文というわけではないので、何をどう書けばいいのかで躓く人が多いです。
ですが、ここまで再帰を書いてきて、その部分は大分分かるようになったのではないでしょうか。
本体が空の再帰も、もしかしたらもう書けるかもしれません。


ここにきて、ようやく再帰とループをそれなりに対等に比べることができるようになったと言えるでしょう。
ループは、その基本形において終了条件を意識する必要性がほとんどありません。
これは再帰に対するループのアドバンテージと言っていいでしょう。


しかし、ループは一回一回の処理、つまりループ本体の処理で何をどうすればいいのかの指針は全くありません。
そのため、空のループまでは書けるけど具体的な処理となると躓く、という人もそれなりにいます。
それに対して、再帰は問題をかなり小さい単位に分割してくれますし、可変の状態を相手にする必要もありません。
そのため、コツさえ掴んでしまえばループを書くよりも再帰を書く方が簡単な問題と言うのも多いです。


効率の面では、ループは今まで見ていた再帰よりも効率的でしょう。
C# 版に至っては、HeadTail によって毎回配列のコピーが発生していますので、更にひどい感じです。
F# に関しては、末尾再帰の形に書き直すことで解決可能です。今回は最終的には間接的に末尾再帰を使うことで、この問題を解決します。


ちなみに一番最初に書いた通り、再帰は最終手段であって、これはあくまで練習です。
再帰に慣れる目標であって、明日からバンバン再帰で書きまくりましょう！という話ではないです*3。
これについては最後にもう一回触れます。


では休憩は終わりです。続けましょう。

skip

先頭から n 個捨て、n + 1 以降の列を返す関数を作ります。

(* int -> 'a list -> 'a list *)
let rec skip n = function
| [] -> []
| x::xs -> ...

public static T[] Skip<T>(T[] xs, int n)
{
    if (xs.Length == 0)
        return new T[0];
    else
    {
        var x_xs = HeadTail(xs); 
        return ...
    }
}

さて、再帰部分はどうしましょう。
とりあえず今まで通り書いてみましょうか。

let rec skip n = function
| [] -> []
| x::xs -> ... (xs |> skip n)

public static T[] Skip<T>(T[] xs, int n)
{
    if (xs.Length == 0)
        return new T[0];
    else
    {
        var x_xs = HeadTail(xs); 
        return ... Skip(x_xs.Item2, n);
    }
}

これだと、... のところをどう書いたとしても無理そうです・・・
実現したいことに戻って考えると、入力の列の先頭から n 個の要素を取り除いた列を作りたいのでした。
で、再帰部分で使えるのは、

  • 先頭の要素 x
  • 先頭より後ろの列 xs
  • スキップしたい数 n

です。
ここで、先頭より後ろの列 xs に対して skip n を行うと、引数の列から一つ減った列から n 個の要素を取り除くことになってしまいます。
先頭の要素はもう取り除かれているので、再帰部分でやりたいのは、「先頭より後ろの列 xs から、n - 1 個の要素を取り除く」ことです。


更に、n が 0 になった場合、(ばらした後の xs ではなく) 引数の xs をそのまま返す必要があります (つまり再帰の終了条件が 2 つある)。
これをコードに落とし込むと、

let rec skip n = function
| [] -> []
| (x::xs) as arg -> if n = 0 then arg
                             else xs |> skip (n - 1)

public static T[] Skip<T>(T[] xs, int n)
{
    if (xs.Length == 0)
        return new T[0];
    else if (n == 0)
        return xs;
    else
    {
        var x_xs = HeadTail(xs); 
        return Skip(x_xs.Item2, n - 1);
    }
}

となります。
さて、F# 版ですが、こう書くこともできます。

let rec skip n = function
| [] -> []
| xs when n = 0 -> xs
| x::xs -> xs |> skip (n - 1)

すっきりしました。
この書き方は C# 版により近い感じです。
他にも、function 式ではなく match 式を使って、

let rec skip n xs =
  match n, xs with
  | _, [] -> []
  | 0, xs -> xs
  | n, _::xs -> xs |> skip (n - 1)

とすることもできます。
この書き方だと、どういうパターンがあるか分かりやすくなっています。


最初の例は、今まで書いてきた再帰の形と同じという意味で分かりやすいです。
二番目の例は、縦にも横にも短く、全体を把握するのが容易です。
最後の例は、終了条件が 2 つある (列が空になった時と、n が 0 の時) というのが分かりやすいです。
この 3 つのどれを選ぶかは個人の好みになります。

練習問題 4
  1. skip では先頭から n 個の要素を捨てましたが、今回はから n 個の要素を取り出す関数 take を書いてください。空の列の扱いや、負数を与えられた場合の挙動は自由とします。
  2. skip では n 個の固定要素を捨てましたが、捨てる条件を指定できる関数 skipWhile を書いてください。
  3. skipWhile の take 版、takeWhile を書いてください。

以降、C# では、以下の関数を使っても構いません。

// 配列の先頭に要素を追加した新しい配列を返す関数
// LISPのcons関数に対応
// consの語源はconstruct(構築する)
public static T[] Cons<T>(T x, T[] xs)
{
    T[] res = new T[xs.Length + 1];
    res[0] = x;
    Array.Copy(xs, 0, res, 1, xs.Length);
    return res;
}
map

全ての要素に変換関数を適用した、新しい列を作り出す関数を作ります。
例えば、「1, 2, 3, 4」という列と「2 倍して文字列化する関数」を map に渡すと、「"2", "4", "6", "8"」になります。

(* ('a -> 'b) -> 'a list -> 'b list *)
let rec map f = function
| [] -> []
| x::xs -> (f x) :: (xs |> map f)

public static U[] Map<T, U>(T[] xs, Func<T, U> f)
{
    if (xs.Length == 0)
        return new T[0];
    else
    {
        var x_xs = HeadTail(xs); 
        return Cons(f(x_xs.Item1), Map(x_xs.Item2, f));
    }
}

一気に書いちゃいました。
この程度の再帰はもう簡単に書き下せるんじゃないでしょうか。
でもそろそろ C# 版が面倒になってきましたので、便利メソッドを追加しましょう。

public static U Match<T, U>(this T[] xs, Func<U> emptyCase, Func<T, T[], U> notEmptyCase)
{
    if (xs.Length == 0)
        return emptyCase();
    else
    {
        var x_xs = HeadTail(xs);
        return notEmptyCase(x_xs.Item1, x_xs.Item2);
    }
}

これで、Item1 や Item2 といったわけのわからない名前を使わなくてよくなります。
例えば、Map を書き直すと

public static U[] Map<T, U>(T[] xs, Func<T, U> f)
{
    return xs.Match(
        () => new T[0],
        (y, ys) => Cons(f(y), Map(ys, f)));
}

と、F# に似た感じに記述することができるようになります*4。
「これがあれば match 式なんていらんかったんやー」とはならない点に注意してください。
Min / Max を書き直そうとした場合、終了条件は「空の列」ではなく、「要素が 1 つの列」なので、別のメソッドを用意する必要が出てきます。
この 2 つだけならまだしも、「空の列」、「要素が 1 つの列」、「それ以外」とそれぞれ必要な場合にはやはり別のメソッドが必要ですし、これを一般化すると必要なメソッド数は膨大になります。
また、ガード条件 (F# での when) を実現することは不可能ではないものの、かなり不恰好なものになってしまいます。
さらに、パターンのネストはどう頑張っても無理です。

練習問題 4 の答
let rec take n = function
| [] | _ when n = 0 -> []
| x::xs -> x :: (xs |> take (n - 1))

let rec skipWhile pred = function
| [] -> []
| x::xs when pred x -> xs |> skipWhile pred
| xs -> xs

let rec takeWhile pred = function
| [] -> []
| x::xs when pred x -> x :: (xs |> takeWhile pred)
| _ -> []

C# 版は、map で導入した Match メソッドを使用することにします。

public static T[] Take<T>(T[] xs, int n)
{
    return xs.Match(
        () => new T[0],
        (y, ys) => n == 0 ? new T[0]
                          : Cons(y, Take(ys, n - 1)));
}

public static T[] SkipWhile<T>(T[] xs, Func<T, bool> pred)
{
    return xs.Match(
        () => new T[0],
        (y, ys) => pred(y) ? SkipWhile(ys, pred)
                           : ys);
}

public static T[] TakeWhile<T>(T[] xs, Func<T, bool> pred)
{
    return xs.Match(
        () => new T[0],
        (y, ys) => pred(y) ? Cond(y, TakeWhile(ys, pred))
                           : new T[0]);
}
練習問題 5

C# 版の今までの関数、

  • Sum
  • Length
  • Max
  • Min
  • Forall
  • Exists
  • Find

を、Match を使って書き直してください。
Min / Max は、別の Match 関数を定義して書き直してください。


F# の人はお休みです。

filter

列の要素のうち、条件を満たす要素のみを残した列を返す関数 filter を作ります。

(* ('a -> bool) -> 'a list -> 'a list *)
let rec filter pred = function
| [] -> []
| x::xs when pred x -> x :: (xs |> filter pred)
| _::xs -> xs |> filter pred

public static T[] Filter<T>(T[] xs, Func<T, bool> pred)
{
    return xs.Match(
        () => new T[0],
        (y, ys) => pred(y) ? Cons(y, Filter(ys, pred))
                           : Filter(ys, pred));
}

今回も一気に書き上げてしまいました。

練習問題 5 の答
public static int Sum(int[] xs)
{
    return xs.Match(
        () => 0,
        (y, ys) => y + Sum(ys));
}

public static int Length<T>(T[] xs)
{
    return xs.Match(
        () => 0,
        (_, ys) => 1 + Length(ys));
}

public static int Max(int[] xs)
{
    return xs.Match(
        y => y,
        (y, ys) => y < Max(ys) ? Max(ys) : y);
}

public static int Min(int[] xs)
{
    return xs.Match(
        y => y,
        (y, ys) => y < Min(ys) ? y : Min(ys));
}

public static bool Forall<T>(T[] xs, Func<T, bool> pred)
{
    return xs.Match(
        () => true,
        (y, ys) => pred(y) && Forall(ys, pred));
}

public static bool Exists<T>(T[] xs, Func<T, bool> pred)
{
    return xs.Match(
        () => false,
        (y, ys) => pred(y) || Exists(ys, pred));
}

public static T Find<T>(T[] xs, Func<T, bool> pred)
{
    return xs.Match(
        () => null,
        (y, ys) => pred(y) ? y : Find(ys, pred));
}

Min / Max の実装に使用した Match 関数の実装はこんな感じです。

public static U Match<T, U>(this T[] xs, Func<T, U> onlyOneElemCase, Func<T, T[], U> elemsCase)
{
    if (xs.Length == 1)
        return onlyOneElemCase(xs[0]);
    else
    {
        var x_xs = HeadTail(xs);
        return elemsCase(x_xs.Item1, x_xs.Item2);
    }
}
練習問題 6

filter では条件を満たさない要素を捨てましたが、条件を満たす要素の列と満たさない要素の列の両方が欲しいこともあります。
それを実現する partition 関数を書いてください。
例えば、「1, 2, 3, 4, 5」という列と「2 で割り切れるか」という関数を渡した場合、(「2, 4」, 「1, 3, 5」) という結果が返ります。
戻り値の型には、タプルを使用してください。

collect

列の全要素に「要素を一つとって新しい列を返す関数」を通し、結果 (列の列) を平坦化して列にする collect 関数を作ります。
言葉で書くと分かりにくいので、ステップごとに追って見ます。
例として、「1, 2, 5」という列と、「0 から指定された数までの連番の列をつくる関数」を collect に渡したとします。
「0 から指定された数までの連番の列をつくる関数」は、例えば 3 を与えると「0, 1, 2, 3」を返します。


まず、「1, 2, 5」から先頭の要素である 1 を処理します。
これを「0 から指定された数までの連番の列をつくる関数」に与えると、「0, 1」となります。
次に、2 を処理すると、「0, 1, 2」となり、5 を処理すると 「0, 1, 2, 3, 4, 5」となります。

元の要素 関数の結果
1 「0, 1」
2 「0, 1, 2」
5 「0, 1, 2, 3, 4, 5」

前に書いた map 関数の場合、戻り値は「「0, 1」, 「0, 1, 2」, 「0, 1, 2, 3, 4, 5」」という列の列になります。
これが、collect の場合平坦化され、「0, 1, 0, 1, 2, 0, 1, 2, 3, 4, 5」という列になります。


動作は分かりましたが、これまでの関数と違い、これが何に使えるかよく分からないかもしれません。
なので、もっと現実に即した例を見てみましょう。
ある関数 f のテストのための入力を考える必要があったとします。
f は、文字列と数値をとる関数で、文字列は空文字列とそうでない文字列とで挙動が異なり、数値は -1 と 0 とそれ以外で挙動が異なるとします。
この関数 f をテストするための入力としては、これらを組み合わせたものが必要となります。
そこで、collect の出番となります。

let names = [""; "one"; "two"]
let values = [-1; 0; 100; 200]

let ans =
  names |> collect (fun name ->
  values |> collect (fun value ->
    [(name, value)]
  ))
(* ans: [("", -1); ("", 0); ("", 100); ("", 200)
         ("one", -1); ("one", 0); ("one", 100); ("one", 200)
         ("two", -1); ("two", 0); ("two", 100); ("two", 200)] *)

このように、collect をネストさせると組み合わせが簡単に作り出せるのです。
手続型言語で書くと、

var names = new[] { "", "one", "two" };
var values = new[] { -1, 0, 100, 200 };

var res = new List<Tuple<string, int>>();
foreach (var name in names)
{
    foreach (var value in values)
    {
        res.Add(Tuple.Create(name, value));
    }
}

このような二重ループになるでしょう。


さて、では書いてみましょう。

(* ('a -> 'b list) -> 'a list -> 'b list *)
let rec collect f = function
| [] -> []
| x::xs -> (f x) @ (xs |> collect f)

public static U[] Collect<T, U>(T[] xs, Func<T, U[]> f)
{
    return xs.Match(
        () => new T[0],
        (y, ys) => Append(f(y), Collect(ys, f)));
}

public static T[] Append<T>(T[] xs, T[] ys)
{
    var res = new T[xs.Length + ys.Length];
    Array.Copy(xs, 0, res, 0, xs.Length);
    Array.Copy(ys, 0, res, xs.Length, ys.Length);
    return res;
}

余裕がある人は、この関数と map の違いを見てみるといいでしょう。
map では :: (C# 版だと Cons) を使っていましたが、collect では @ (C# 版だと Append) になっています。
collect に合わせて、map に渡す f の戻り値の型を何らかの列にしたとします。
その場合に、map だと関数呼び出しの結果を後続の列と :: でつなげますので、map の戻り値の型は列の列になるのです。
それに対して collect だと、関数呼び出しの結果を後続の列と @ でつなげますので、collect の戻り値の型は列になります。
ちなみに、collect のネストで紹介したコードですが、実は一番内側の collect は map を使うと更に単純になります。

let names = [""; "one"; "two"]
let values = [-1; 0; 100; 200]

let ans =
  names |> collect (fun name ->
  values |> collect (fun value ->
    [(name, value)]
  ))

let ans2 =
  names |> collect (fun name ->
  values |> map (fun value ->
    (name, value)    (* collectと異なり、リストで包む必要はない *)
  ))
練習問題 6 の答
let rec partition pred = function
| [] -> [], []
| x::xs ->
    let t, f = xs |> partition pred
    if pred x then (x::t, f)
              else (t, x::f)

public static Tuple<T[], T[]> Partition<T>(T[] xs, Func<T, bool> pred)
{
    return xs.Match(
        () => Tuple.Create(new T[0], new T[0]),
        (y, ys) => {
            var t_f = Partition(ys, pred);
            var t = t_f.Item1;
            var f = t_f.Item2;
            return pred(y) ? Tuple.Create(Cons(y, t), f)
                           : Tuple.Create(t, Cons(y, f));
        });
}

タプルがパターンマッチ、それも let の部分でばらせるので、F# 版素晴らしいですね。
タプルに対して Let 関数を用意したとしても、

public static Tuple<T[], T[]> Partition<T>(T[] xs, Func<T, bool> pred)
{
    return xs.Match(
        () => Tuple.Create(new T[0], new T[0]),
        (y, ys) =>
            Partition(ys, pred).
            Let((t, f) => pred(y) ? Tuple.Create(Cons(y, t), f)
                                  : Tuple.Create(t, Cons(y, f))));
}

微妙な所ですね・・・

練習問題 7

map と filter を一度に行う choose 関数を書いてください。
map 関数に渡す関数 f の戻り値は、map 自体の戻り値となる列の各要素の型でした。
これだと filter できないので、それを更に option という型で包むことで、None の場合は結果から除外することにします。
例えば、「1, 2, 3, 4, 5」という列と「偶数は 2 倍して返し、奇数は None を返す」関数を渡すと、「4, 8」という列が返ります。
C# では次のクラスを使います。

// 偶数は2倍して返し、奇数はNoneを返す関数は、
// Func<int, Option<int>> f =
//     i => i % 2 == 0 ? Make.Some(i * 2)
//                     : Make.None<int>();
// のように書きます。
public static class Make
{
    public static Option<T> Some<T>(T value) { return new Option<T>.Some<T>(value); }
    public static Option<T> None<T>() { return new Option<T>.None<T>(); }
}
// 値があるかないかで処理を分岐させたい場合は、
// opt.Match(
//     value => /* 値がある場合の処理 */,
//     ()    => /* 値がない場合の処理 */);
// のように書きます。
public abstract class Option<T>
{
    public abstract U Match<U>(Func<T, U> ifSome, Func<U> ifNone);
    public sealed class Some<T> : Option<T>
    {
        readonly T value;
        public Some(T value) { this.value = value; }
        public override U Match<U>(Func<T, U> ifSome, Func<U> _) { return ifSome(value); }
    }
    public sealed class None<T> : Option<T>
    {
        public override U Match<U>(Func<T, U> _, Func<U> ifNone) { return ifNone(); }
    }
}
foldBack / reduceBack

さて、ここまでたくさんの再帰関数を見てきました。
これから書く foldBack / reduceBack は、今まで見てきた再帰関数の共通点を抽出し、可変な部分を引数として受け取るようにした関数です。
各再帰関数で可変な部分とはどこでしょうか？
それは、「初期値」と「再帰部分での計算」です。


分かりにくい関数もあるので、分かりやすい関数から見ていきましょう。
sum、forall、map、partition あたりを見てみましょうか。

let rec sum = function
| [] -> 0
| x::xs -> x + (sum xs)

let rec forall pred = function
| [] -> true
| x::xs -> (pred x) && (xs |> forall pred)

let rec map f = function
| [] -> []
| x::xs -> (f x) :: (xs |> map f)

let rec partition pred = function
| [] -> [], []
| x::xs ->
    let t, f = xs |> partition pred
    if pred x then (x::t, f)
              else (t, x::f)

public static int Sum(int[] xs)
{
    return xs.Match(
        () => 0,
        (y, ys) => y + Sum(ys));
}

public static bool Forall<T>(T[] xs, Func<T, bool> pred)
{
    return xs.Match(
        () => true,
        (y, ys) => pred(y) && Forall(ys, pred));
}

public static U[] Map<T, U>(T[] xs, Func<T, U> f)
{
    return xs.Match(
        () => new T[0],
        (y, ys) => Cons(f(y), Map(ys, f)));
}

public static Tuple<T[], T[]> Partition<T>(T[] xs, Func<T, bool> pred)
{
    return xs.Match(
        () => Tuple.Create(new T[0], new T[0]),
        (y, ys) =>
            Partition(ys, pred).
            Let((t, f) => pred(y) ? Tuple.Create(Cons(y, t), f)
                                  : Tuple.Create(t, Cons(y, f))));
}

どうでしょう、可変部分は見えましたか？
可変部分を表にまとめると、以下のようになります。

関数 初期値 再帰部分での計算
sum 0 加算
forall true 論理積
map 空の列 列の先頭に要素を追加
partition 2 つの空の列 条件を満たす場合は一つ目の列の先頭に、満たさない場合は二つ目の列の先頭に追加

ではこれを引数に受け取れるような関数 foldBack を作ってみましょう。
まず、再帰部分での計算の型を考えます。

  1. 計算を表すということなので、何らかの関数と言うことになるでしょう(* -> *、もしくは Func<*, *>)
  2. 引数としては、「現在の要素」と、「1 つ前までの計算結果」の 2 つが必要になります('a -> 'b -> *、もしくはFunc)
  3. この計算で求めた結果は、1 つ後の計算の時に「1 つ前までの計算結果」として使われますので、関数の型が 'a -> 'b -> 'b、もしくは Func に決まります

次に初期値ですが、再帰の一番奥、空の列の時の値として初期値を使いますので、計算の型の第一引数と同じになります。
つまり、'b もしくは U です。


後は、要素の型が 'a もしくは T なので、

F#
('a -> 'b -> 'b) -> 'a list -> 'b -> 'b
C#
U Fold(T[] xs, U init, Func f)

となります。
ではコードに落とし込んでみましょう。

(* ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b *)
let rec foldBack f xs init =
  match xs with
  | [] -> init
  | x::xs -> f x ((xs, init) ||> foldBack f)

// 今までとは違い、拡張メソッドとして定義しておく
public static U FoldBack<T, U>(this T[] xs, U init, Func<T, U, U> f)
{
    return xs.Match(
        () => init,
        (y, ys) => f(y, FoldBack(ys, init, f)));
}

できました！
では foldBack を使って、さっき表にした関数を書き直してみます。

let sum xs = (xs, 0) ||> foldBack (fun x xs -> x + xs)
let forall pred xs = (xs, true) ||> foldBack (fun x xs -> (pred x) && xs)
let map f xs = (xs, []) ||> foldBack (fun x xs -> (f x) :: xs)
let partition pred xs =
  (xs, ([], [])) ||> foldBack (fun x (t, f) -> if pred x then (x::t, f)
                                                         else (t, x::f))

public static readonly Func<int[], int> Sum =
    xs => xs.FoldBack(0, (y, ys => y + ys));

public static bool Forall<T>(T[] xs, Func<T, bool> pred)
{
    return xs.FoldBack(true, (y, ys) => pred(y) && ys);
}

public static U[] Map<T, U>(T[] xs, Func<T, U> f)
{
    return xs.FoldBack(new T[0], (y, ys) => Cons(f(y), Map(ys, f)));
}

public static Tuple<T[], T[]> Partition<T>(T[] xs, Func<T, bool> pred)
{
    // 今までMatchで書いてきたコードとそれなりに似ているが、
    // Matchよりもできることは少ない(条件によって再帰しないようにしたりとかはできない)
    // しかし、能力を制限することによって、間違いを犯す可能性は少なくなっている
    return xs.FoldBack(
        Tuple.Create(new T[0], new T[0]),
        (y, ys) => pred(y) ? Tuple.Create(Cons(y, ys.Item1), ys.Item2)
                           : Tuple.Create(ys.Item1, Cons(y, ys.Item2)));
}

このように、foldBack があればほとんどの再帰は不要になります。
でも何か忘れていませんか？
min と max です。
こいつらは、foldBack の兄弟である reduceBack を使うことで書き直せるようになります。
reduceBack は、初期値として列の要素が 1 つのとき (再帰の最後の要素、要は列の末尾要素) を使います。

(* ('a -> 'a -> 'a) -> 'a list -> 'a *)
let rec reduceBack f = function
| [x] -> x
| x::xs -> f x (xs |> reduceBack f)
| [] -> invalidArg "入力リストが空でした。" "xs"

public static T[] ReduceBack<T>(this T[] xs, Func<T, T, T> f)
{
    return xs.Match(
        y => y,
        (y, ys) => f(y, ReduceBack(ys, f)));
}
練習問題 7 の答
let rec choose f = function
| [] -> []
| x::xs ->
    match f x with
    | Some x -> x :: (xs |> choose f)
    | None -> xs |> choose f

public static U[] Choose<T, U>(T[] xs, Func<T, Option<U>> f)
{
    return xs.Match(
        () => new T[0],
        (y, ys) =>
            f(y).Match(
                value => Cons(value, Choose(ys, f)),
                () => Choose(ys, f)));
}
練習問題 8

今までの関数を、foldBack もしくは reduceBack を使って書き直してください。
ただし、skip / take は除きます。

fold / reduce

foldBack と reduceBack についていた「Back」とはどういうことでしょうか？
これは、再帰がどのような順番で行われるのかを考えると分かりやすいです。
例えば、

[1..5] |> reduceBack (fun a b -> a + b)

Enumerable.Range(1, 5).ToArray().Reduce((a, b) => a + b);

を考えてみましょう。
最初は「1, 2, 3, 4, 5」という入力なので、x は 1、xs は「2, 3, 4, 5」です。
f は 「x + 再帰の結果」なので、「1 + (再帰の結果)」となります。
次は再帰の結果を見ていきます。
「2, 3, 4, 5」という入力なので、x は 2、xs は「3, 4, 5」です。
上の「再帰の結果」としたところは、「2 + (再帰の結果2)」となります。
全体では、「1 + (2 + (再帰の結果2))」です。
これを順番に辿っていくと、「1 + (2 + (3 + (4 + (5))))」となります。
この式の計算の順番を見ると、列の「後ろから」計算が行われていくのが分かります。
これが、Back の意味です。


では、列の「前から」計算が行われるような関数 fold / reduce を作りましょう。

(* ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a *)
let rec fold f init = function
| [] -> init
| x::xs -> xs |> fold f (f init x)

(* ('a -> 'a -> 'a) -> 'a list -> 'a *)
let reduce f (x::xs) = xs |> fold f x

public static U Fold<T, U>(this T[] xs, U init, Func<U, T, U> f)
{
    return xs.Match(
        () => init,
        (y, ys) -> Fold(ys, f(init, y), f));
}

public static T Reduce<T>(this T[] xs, Func<T, T, T> f)
{
    return xs.Match(
        () => throw new Exception(),
        (y, ys) => ys.Fold(y, f));
}

さて、fold / reduce と foldBack / reduceBack を作ったわけですが、これらの違いはなんでしょうか？
もっとも分かりやすい違いは、結合の方向でしょう。
例えば、

[1..5] |> reduce (-)
[1..5] |> reduceBack (-)

Enumerable.Range(1, 5).ToArray().Reduce((a, b) => a + b);
Enumerable.Range(1, 5).ToArray().ReduceBack((a, b) => a + b);

とした場合、

reduce
「(((1 - 2) - 3) - 4) - 5」 = -13
reduceBack
「1 - (2 - (3 - (4 - 5)))」 = 3

となり、結果が異なります。


他にも、末尾最適化が効くかどうか、という違いもあります。
fold / reduce は末尾再帰の形になっているため、末尾最適化が働き、再帰がループと同等のコードとしてコンパイルされます。
そのため、fold / reduce は foldBack / reduceBack と違い、スタックオーバーフローが起こりません*5。
以下のコードを実行してみるとそれがよく分かるでしょう。

open System.Diagnostics

let rec fold f init xs =
  match xs with
  | [] -> StackTrace() |> printfn "%A"; init
  | x::xs -> xs |> fold f (f init x)

let reduce f (x::xs) = xs |> fold f x

let rec reduceBack f xs =
  match xs with
  | [x] -> StackTrace() |> printfn "%A"; x
  | x::xs -> f x (xs |> reduceBack f)
  | [] -> invalidArg "入力リストが空でした。" "xs"


let xs = [1..10]

printfn "reduce"
let _ = xs |> reduce (+)

printfn "reduceBack"
let _ = xs |> reduceBack (+)

ちなみに、OCaml では fold は fold_left、foldBack は fold_right と呼びます。
この「右」「左」というのは結構重要で、

  1. 右結合の演算子 (::) は fold_right の相性がいい
  2. アキュムレータ (途中の計算結果) がラムダ式のどちらの引数かは fold_right の場合右に、fold_left の場合左に来ると覚えると覚えやすい

という利点があります。
最初の点については、fold (fold_left に相当) で map や filter など、:: (もしくは Cons) を使う関数を書いてみると分かりやすいでしょう。
右結合の演算子を左から畳み込むため、そのまま書くと結果が反転してしまうのです。

練習問題 8 の答
let sum xs = (xs, 0) ||> foldBack (+)
let length xs = (xs, 0) ||> foldBack ((+)1)

let max xs = xs |> reduceBack (fun a b -> if a < b then b else a)
let min xs = xs |> reduceBack (fun a b -> if a < b then a else b)

let forall pred xs = (xs, true) ||> foldBack (fun x acc -> (pred x) && acc)
let exists pred xs = (xs, false) ||> foldBack (fun x acc -> (pred x) || acc)

let find pred xs = (xs, null) ||> foldBack (fun x acc -> if pred x then x else acc) 

(* skip/takeはやってなくてもOKです *)
(* 関数を使って実現 *)
let skip n xs =
  let f x g = function
  | 0 -> x :: (g 0)
  | n -> g (n - 1)
  foldBack f xs (fun _ -> []) n
let take n xs =
  let f x g = function
  | 0 -> []
  | n -> x :: (g (n - 1))
  foldBack f xs (fun _ -> []) n

let skipWhile pred xs =
  (xs, [])
  ||> foldBack (fun x xs -> if pred x then [] else x::xs)
let takeWhile pred xs =
  (xs, [])
  ||> foldBack (fun x xs -> if pred x then x::xs else [])

let map f xs = (xs, []) ||> foldBack (fun x xs -> (f x) :: xs)

let filter pred xs = (xs, []) ||> foldBack (fun x xs -> if pred x then x::xs else xs)
let partition pred xs =
  (xs, ([], [])) ||> foldBack (fun x (t, f) -> if pred x then (x::t, f)
                                                         else (t, x::f))

let collect f xs = (xs, []) ||> foldBack (fun x xs -> (f x) @ xs)
let choose f xs =
  (xs, []) ||> foldBack (fun x xs ->
    match f x with
    | Some x -> x::xs
    | None -> xs)

public static readonly Func<int[], int> Sum =
    xs => xs.FoldBack(0, (x, acc => x + acc));
public static int Length<T>(T[] xs)
{
    return xs.FoldBack(0, (_, acc) => 1 + acc);
}

public static int Max(int[] xs)
{
    return xs.ReduceBack((x, acc) => x < acc ? acc : x);
}
public static int Min(int[] xs)
{
    return xs.ReduceBack((x, acc) => x < acc ? x : acc);
}

public static bool Forall<T>(T[] xs, Func<T, bool> pred)
{
    return xs.FoldBack(true, (x, acc) => pred(x) && acc);
}
public static bool Exists<T>(T[] xs, Func<T, bool> pred)
{
    return xs.FoldBack(false, (x, acc) => pred(x) && acc);
}

public static T Find<T>(T[] xs, Func<T, bool> pred)
{
    return xs.FoldBack(null, (x, acc) => pred(x) ? x : acc);
}

// skip / take はF#版を参考にしてください

public static T[] SkipWhile<T>(T[] xs, Func<T, bool> pred)
{
    return xs.FoldBack(new T[0], (y, ys) => pred(y) ? new T[0] : Cons(y, ys));
}
public static T[] TakeWhile<T>(T[] xs, Func<T, bool> pred)
{
    return xs.FoldBack(new T[0], (y, ys) => pred(y) ? Cons(y, ys) : new T[0]);
}

public static U[] Map<T, U>(T[] xs, Func<T, U> f)
{
    return xs.FoldBack(new T[0], (y, ys) => Cons(f(y), ys));
}

public static T[] Filter<T>(T[] xs, Func<T, bool> pred)
{
    return xs.FoldBack(new T[0], (y, ys) => pred(y) ? Cons(y, ys) : ys);
}
public static Tuple<T[], T[]> Partition<T>(T[] xs, Func<T, bool> pred)
{
    return xs.FoldBack(
        Tuple.Create(new T[0], new T[0]),
        (y, ys) => pred(y) ? Tuple.Create(Cons(y, ys.Item1), ys.Item2)
                           : Tuple.Create(ys.Item1, Cons(y, ys.Item2)));
}

public static U[] Collect<T, U>(T[] xs, Func<T, U[]> f)
{
    return xs.FoldBack(new T[0], (y, ys) => Append(f(y), ys));
}
public static U[] Choose<T, U>(T[] xs, Func<T, Option<U>> f)
{
    return xs.FoldBack(
        new T[0],
        (y, ys) => f(y).Match(
            value => Cons(value, ys),
            () => ys));
}
練習問題 9

練習問題 9 は、答を用意していません。
各自納得のできる答を考えることができたら、それで良しとします。

  1. F# の List.scan / List.scanBack を調べ、自身で実装してください。この関数は何に使えるでしょうか？
  2. F# のリストの表現として、箱を矢印で繋いだ表現がふさわしくない理由を考えてください。ヒントはリスト同士の連結の計算量です。
  3. C# では配列を作りまくりました。この回数を減らすことは可能でしょうか？可能だとしたら、それはどのようにすればいいですか？
  4. もう一回このエントリを読み直してみてください。新しい発見はありましたか？

まとめ

お疲れ様でした。
ここまで理解できれば、よく出会うであろう終了条件と再帰部を持つような再帰については怖いものなしです。
木構造に対する再帰関数なども、すんなり書けるようになっているはずです。
また、再帰ではなく、fold や foldBack と言った関数もある程度使えるようになったのではないでしょうか？


で、ですね。
最初でも途中でも言ったことですが、再帰は最後の手段です。
再帰を書くよりも、より力の制限された fold 系の関数で書けないか考えるべきです。
fold 系の関数を使って書くよりも、より力の制限された (目的に特化した) 関数で書けないか考えるべきです。
なぜか。
その方が分かりやすくなるからです。

(* 再帰で *)
let rec f = function
| [] -> []
| x::xs -> (x + 10) :: (f xs)

(* foldで *)
let f xs =
  (xs, []) ||> List.foldBack (fun x xs -> (x + 10)::xs)

(* mapで *)
let f xs = xs |> List.map ((+)10)

明らかに一番最後が一番わかりやすいうえ、間違いも起こりえないですよね。
再帰で書く場合は、再帰呼び出しを忘れずに行う必要がありますし、答を作り出すためにどういう計算を行えばいいのかを考える必要もあります。
fold 系関数で書く場合は、再帰呼び出しがカプセル化するため呼び忘れはありませんが、依然どういう計算を行えばいいのかを考える必要はあります。
それらに対して、問題解決により特化した関数 (ここでは map) を使うことで、短く、分かりやすいコードを書くことが可能です。


どういう場面でどういう関数が使えるのかを身に付けるためには、その関数を何度も使うのが一番の近道です。
F# であれば、List モジュールや Seq モジュールの関数を、C# であれば LINQ to Objects のメソッドをどんどん使っていきましょう。
そして、再帰は最後の手段として、ここだ！というときにのみ使うようにしましょう。

他の道

再帰に至る他の道もいくつか紹介しておきます。

なぜ関数プログラミングは重要か
「3 関数の貼り合わせ」の部分がこのエントリの元ネタ。sum の例だけから fold に飛んでいるため鬼。
C#開発者のためのやさしい「再帰」再入門 ― F#開発者ならこう考える − ＠IT
上では最初から再帰を用いたが、この記事ではループから末尾再帰への変換というアプローチで再帰に迫る。
プログラミングの基礎 (Computer Science Library)
書籍。デザインレシピと言いう考え方。
関数プログラミングの道しるべ (PDF)
30 ページから。45 ページからの「力の階層と節度」はまとめ部分と同じ。


次は連載に戻ります。

*1:ちなみに、ここでは再帰呼び出しの再帰を扱い、再帰的なデータ構造については扱いません。

*2:拡張メソッドもそうなっています。

*3:いや、まぁ、慣れるまではバンバン使えばいいと思います。人の迷惑にならない部分で。

*4:F# と違い、C# ではローカル変数のシャドウイングが出来ないため、x, xs は使えません・・・

*5:ただし、F# の List.foldBack / List.reduceBack はスタックオーバーフローが起こらない実装になっています。