PHP で Y コンビネータ

Tomohiro wrote this on Mar 31, 2011

Y コンビネータ関数を作る

PHP で Y コンビネータ [Y(F) = F(Y(F))] を行う関数 Y を定義してみる．

以下のコードは PHP 5.3+ な環境で動作する．

<?php
function Y($F) {
    return $F(
        function() use($F) {
            return call_user_func_array(Y($F), func_get_args());
        }
    );
}

Y コンビネータを使用して無名な再帰関数を作る

階乗

<?php
echo Y(
    function($fact) {
        return function($x) use ($fact) {
            return $x == 1 ? 1 : $x * $fact($x - 1);
        };
    })->__invoke(10); // 3628800

フィボナッチ数

<?php
echo Y(
    function($fib) {
        return function($n) use ($fib) {
            return $n <= 2 ? 1 : $fib($n - 1) + $fib($n - 2);
        };
    })->__invoke(10); // 55

ハノイの塔

<?php
Y(
    function($hanoi) {
        return function($n, $a, $b, $c) use ($hanoi) {
            if ($n > 0) {
                $hanoi($n - 1, $a, $c, $b);
                echo "No. $n disk is moved from $a to $b" . PHP_EOL;
                $hanoi($n - 1, $c, $b, $a);
            }
        };
    }
)->__invoke(64, 'A', 'B', 'C');

References