F#/OCamlのrecのサンプルコード(JS付き)

ぼーっと2chの過去ログを読んでたら、こんなコードを見付けたのでめも。

727 名前: デフォルトの名無しさん Mail: sage 投稿日: 2010/02/16(火) 01:16:04

下みたいにrecの有無で結果が変わる場合もある。
束縛の再定義が嫌な人もいるだろうけど、個人的には便利。

let square n =
    let f x = x + 1
    let f = function 1 -> 1 | x -> x * f (x - 1)
    f n

let factorial n =
    let f x = x + 1
    let rec f = function 1 -> 1 | x -> x * f (x - 1)
    f n

printfn "5^2 = %d, 5! = %d" (square 5) (factorial 5)

言っておくとこれは黒魔術的におもしろく見えるだけであって、別に良いコードではない。しかし、recのありなしで振舞ひがどう変化するかはよくわかる。飽くまでサンプルコード。

それぞれ何が起こってゐるのかについて、半年前の自分に説明するつもりで註釈を入れてみる。

とりあへずこれはOCamlでもだいたい共通してるので、OCamlで、ちょっと冗長にして書き換へて考へてみる。

open Printf

let square = fun n ->
    let f x = x + 1 in
    let f = function
        | 1 -> 1
        | x -> x * f (x - 1) in
    f n ;;

let factorial = fun n ->
    let f x = x + 1 in
    let rec f = function
        | 1 -> 1
        | x -> x * f (x - 1) in
    f n ;;

printf "5^2 = %d, 5! = %d\n" (square 5) (factorial 5)

このコードは、OCamlの処理系がなくてもF#でも、拡張子 ml のファイルに保存すれば実行できる、と思ふ。あるいはideoneでもおｋ。

inキーワードは冗長でもあるけど、これがないとOCaml本来の構文の本質を見失ふおそれがあるので大事。書くときは簡潔に書けるF#の軽量構文(lightweight syntax)の方がきっと便利だけど。

letキーワードは、値に名前(変数名)を束縛する。

まったく等価ではないけれど、funに束縛することで、JavaScriptでvar func = function () { ... };とやるのと同じ考へかたで函数定義してる。

functionは引数のタイプによって場合分けする函数の定義で、funとmatchを組み合せたやうなものを、もっと簡潔に書くことができる。

今回のケースに限って言ふならば、function 1 -> 1 | x -> x * f (x - 1)は、JavaScriptのif (x == 1) return 1; else return x * f(x - 1);と等価だけれど、もっとmatch及びfunctionはもっと柔軟に使用できるので注目されたい。

で、今回の主役のrecさん。このキーワードを付けて束縛すると、束縛される函数の定義内でその名前(変数名)を参照することができる。つまり、自分自身を呼び出すことができるやうになる。recはもちろん "recursion" "recursive" の「再帰」。

最後に、函数とinキーワードの説明は…みんな大好き、僕も大好きなJavaScriptで意味論的に(ほぼ((letとvarは似てるけど、束縛と代入で異なる)) )等価なコードで。

var square = function (n) {
    return function () {
        var f = function (x) { return x + 1; };
        return function () {
            var g = function (x) {
                if (x == 1) {
                    return 1;
                } else {
                    return x * f(x - 1);
                }
            };
            return function () {
                return g(n);
    }(); }(); }();
};

var factorial = function (n) {
    return function () {
        var f = function (x) { return x + 1; };
        return function () {
            var g = function (x) {
                if (x == 1) {
                    return 1;
                } else {
                    return x * g(x - 1);
                }
            };
            return function () {
                return g(n);
    }(); }(); }();
};

束縛は常にスコープを持ち、函数定義の中での束縛はローカルな変数として取り扱はれる。F#/OCaml/JavaScriptのどの例においてもfやgは定義の外側からは参照できない。

もちろん、等価を目指さなければ即時実行函数 return function () { ... }();は全て省ける。しかしF#/OCamlでは最後に評価した値を函数の返り値とするので、このやうに書くのが正確であるやうに思ふ。

JavaScriptはrec相当のものはなく、そのままで再帰できる。一方でF#/OCamlではプログラマが明示しないと再帰はできないやうになってゐる。