学生エンジニア小話

プログラミングのお話

PHPで関数型ぽいイミュータブルなリストを実装してみる

f:id:takuseno:20161115152624j:plain

大学のコンパイラについての授業でOCamlを使っているのですが、そこでイミュータブルなリストを関数で定義していて感心しました。

そこで、アルバイト先で使っているPHPで同じものを再現してみました。

コード

<?php
$update = function ($var, $vl, $t) {
    return function ($x) use ($var, $vl, $t) {
        if ($x == $var) {
            return $vl;
        }
        return $t($x);
    };
};

$initTable = function () {
    return function ($x) {
        echo "no variables\n";
    };
};

$l1 = $update('a', 1, $initTable());
$l2 = $update('b', 2, $l1);

echo $l2('a')."\n";
echo $l2('b')."\n";
$l2('c');

// 1
// 2
// no variables

解説

update関数で毎回関数を返しています。その関数は値を返すかさらに関数を読んでいます。

このままではわかりにくいので、実際にリストにabが登録された時の様子var_dump($l2)を行った結果としてみてみましょう。

object(Closure)#5 (2) {
  ["static"]=>
  array(3) {
    ["var"]=>
    string(1) "b"
    ["vl"]=>
    int(2)
    ["t"]=>
    object(Closure)#4 (2) {
      ["static"]=>
      array(3) {
        ["var"]=>
        string(1) "a"
        ["vl"]=>
        int(1)
        ["t"]=>
        object(Closure)#3 (1) {
          ["parameter"]=>
          array(1) {
            ["$x"]=>
            string(10) "<required>"
          }
        }
      }
      ["parameter"]=>
      array(1) {
        ["$x"]=>
        string(10) "<required>"
      }
    }
  }
  ["parameter"]=>
  array(1) {
    ["$x"]=>
    string(10) "<required>"
  }
}

Closureオブジェクトがネストをなしているのがわかりますね。

updateを実行するたびにどんどん関数のネストを掘り下げている感じです。これで引数のリストに影響を与えずに新しいリストを生成するイミュータブルな関数型らしいリストをPHPで実装することができました。

しかし、パフォーマンスはかなり悪く、PHPでは深すぎると関数を呼びすぎてスタックがいっぱいになってしまうかもしれません。

まとめ

関数型の言語でないと実用性はないですが、普段関数型に触れないエンジニアのかたにはなかなか面白いと感じられると思います。

ちなみにOcamlでの実装はこれだけシンプルになります。

let initTable = fun x -> raise No_such_variable
let update var vl t = fun x -> if x = var then vl else t x