PHPで関数型ぽいイミュータブルなリストを実装してみる
大学のコンパイラについての授業で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
関数で毎回関数を返しています。その関数は値を返すかさらに関数を読んでいます。
このままではわかりにくいので、実際にリストにa
、b
が登録された時の様子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