不動点コンビネータを用いた無名再帰関数の実行(C#, F#)

19068 ワード
F# 再帰 C# ラムダ式 F# テキストリンク

cf. 不動点コンビネータを用いた無名再帰関数の実行まとめ

不動点コンビネータとは

すごく簡単に言うと、「再帰じゃない関数を引数にとって、再帰関数と同じ動きをする関数に作り替えてくれる高階関数」です。

再帰関数の例として、例えばフィボナッチ数を返す関数をJavaScriptで書いてみると

function fibonacci(n) {
  if (n == 0) return 0;
  else if (n == 1) return 1;
  else return fibonacci(n-1) + fibonacci(n-2);
}

と書いてもいいわけですが、記事の都合で末尾再帰の形にして

function fibonacci(f1, f2, counter) {
  if (counter == 0) return f1;
  else return fibonacci(f2, f1+f2, counter-1);
}
function fibonacci_(n) {
  return fibonacci(0, 1, n);
}

とまあこんな感じの末尾再帰にしたfibonacciを、さらにカリー化して例にします。

上のfibonacciはfunctionで定義されていますが、これをカリー化したアロー関数（匿名関数）で書きたい場合は

const fibonacci = f1 => f2 => n => (n == 0) ? f1 : fibonacci(f2)(f1+f2)(n-1);

こんな感じで、再帰するには一旦fibonacciという名前の変数を作っておいてから書き換えてやらないといけないと思ったがそんなことはなかったぜ。

ここに不動点コンビネータであるfix関数があれば

const fix = /* ... */
const f = fib => f1 => f2 => n => (n == 0) ? f1 : fib(f2)(f1+f2)(n-1); // fは再帰関数ではない
const fibonacci = fix f

こんな感じで、再帰してないアロー関数（匿名関数）fを使って再帰関数fibonacciができあがります。

不動点コンビネータがあると嬉しい、というようなものではないのですが、まあ計算理論として興味深い、というぐらい。

不動点コンビネータ - Wikipediaも読んでおくといいでしょう。

不動点コンビネータその1 再帰関数で実装したもの

fixの方を再帰定義にしてよければ、割と簡単です。

ただし、引数を名前呼び（遅延評価）する言語と値呼び（正格評価）する言語でちょっと書き方が変わります。

C# と F# はどちらも後者になります。

fixの型を疑似的に表すと ((T1 => T2) => (T1 => T2)) => (T1 => T2) です。

C#の例です。Fixをスタティックメソッドにしておきました。
Fixを呼び出しているところの型引数Fix<int, Func<int, Func<int, int>>>がうっとうしいですが、C#のラムダ式には型がなく、外から与えてやる必要があるので、仕方ありません。型引数を省略しようとすると、今度はラムダ式をキャストして、型を明示しないといけません。

Fibonacci.cs
using System;

class Program
{
    static void Main(string[] args)
    {
        int fib40 = Fix<int, Func<int, Func<int, int>>>(fib => f1 => f2 => n => n == 0 ? f1 : fib(f2)(f1 + f2)(n - 1))(0)(1)(40);
        Console.WriteLine(fib40);
    }

    // name "Fix" is recursive
    static Func<T1, T2> Fix<T1, T2>(Func<Func<T1, T2>, Func<T1, T2>> f) =>
        f(x => (Fix(f))(x));
}

F# はOCamlベースで、カリー化されていて、型推論も強力なのですっきりしています。

Fibonacci.fs
let rec fix f =
    f (fun x -> fix f x)

let fib40 =
    fix (fun fib f1 f2 n -> if n = 0 then f1 else fib f2 (f1 + f2) (n - 1)) 0 1 40

不動点コンビネータその2 Zコンビネータ―で実装したもの

不動点コンビネータ―fixの方も再帰なしで定義する例として、有名なのはYコンビネーターですが、静的型付け言語だとYコンビネーターにはうまく型が付けられないので、代わりにZコンビネータ―を定義します。

Zコンビネータ―は、関数は再帰しませんが、型の定義が再帰します。

C# や F# では、独自のデリゲート型を定義することで、型の定義が再帰するような関数やメソッドの型を用意できます。ただ、デリゲート型をF#で扱うのはちょっとだけぎこちなくなります。

C# はこちら。Zの定義の中でラムダ式をRecursive<T1, T2>デリゲート型にキャストする形で型を明示しています。

FibonacciZ.cs
using System;

// type "Recursive<T1, T2>" is recursive
delegate Func<T1, T2> Recursive<T1, T2>(Recursive<T1, T2> f);

class Program
{
    static void Main(string[] args)
    {
        int fib40 = Z<int, Func<int, Func<int, int>>>(fib => f1 => f2 => n => n == 0 ? f1 : fib(f2)(f1 + f2)(n - 1))(0)(1)(40);
        Console.WriteLine(fib40);
    }

    static Func<T1, T2> Z<T1, T2>(Func<Func<T1, T2>, Func<T1, T2>> f) =>
        ((Recursive<T1, T2>)(g => f(x => g(g)(x))))
        ((Recursive<T1, T2>)(g => f(x => g(g)(x))));
}

F# はこちら。デリゲート型をインスタンス化し、呼び出しにInvokeメソッドを使うなど、オブジェクト指向的なデリゲート型の扱いがC#よりもあからさまになっています（C# もバージョン1の頃はnewでデリゲート型をインスタンス化していました）。

FibonacciZ.fs
// type "Recursive<'a, 'b>" is recursive
type Recursive<'a, 'b> =
    delegate of Recursive<'a, 'b> -> ('a -> 'b)

let z f =
    (Recursive(fun g -> f (fun x -> g.Invoke g x))).Invoke
        (Recursive(fun g -> f (fun x -> g.Invoke g x)))

let fib40 =
    z (fun fib f1 f2 n -> if n = 0 then f1 else fib f2 (f1 + f2) (n - 1)) 0 1 40

printfn "%d" fib40