高階関数がなす圏上の自己関手Fとして、型Xを A+X*X へ移すものを考える。A+X*X は具体的には、$a∈A 、$x1, $x2∈X としたとき、$a または ($x1, $x2) の形を含むもの。
F代数とは、FX→X のような射をいう。例えば、以下のような射A+Int*Int→Int。
sub choose_max($;$) { @_ == 1 ? 1 # type A : max($_[0], $_[1]) + 1; # type Int*Int }
2つのF代数FX→XとFY→Yについて、f:X→Y の中でfとFfが作る四角形の図式を可換にする物をF代数の間の射と見なせる。こうすることで、F代数は圏となる。
Tree Aを型Aの葉がなす二分木とする。具体的には、[$a1, [ [$a2, $a3], $a4] ] のようにスカラと要素数が2つの配列リファレンスからなっているもの全て。
F代数がなす圏の中で、以下のF代数A+Tree A*Tree A→Tree Aは始対象となる*1。
sub tree($;$) { @_ == 1 ? $_[0] # type A (Leaf) : [$_[0], $_[1]]; # type Tree A*Tree A (Branch) }
treeが始対象なので、F代数がなす圏の中でtreeからchoose_maxには射が唯一存在する。これをcatamorphism と呼ぶ。fold_tree:(FX→X)→Tree A→X を以下のように定義すると、この関数がF代数からcatamorphism を算出する関数となる。
use Scalar::Util (); sub fold_tree($) { my $f = shift; my $result = $collee = sub { my $tree = shift; ref $tree ? $f->($collee->($tree->[0]), $collee->($tree->[1])) # Branch : $f->($tree); # Leaf }; Scalar::Util::weaken $collee; $result; }
先のchoose_max のcatamorphism を求めると、ツリーの深さを求める関数となる。
print +(fold_tree \&choose_max)->([1, [2, [[3, 4], 5]]]), "\n"; # The result is 5
F始代数 tree へのcatamorphism は、catamorphism の唯一性からid となる。つまり、入力値を何も変えずに出力するだけである。
{
use Data::Dumper;
local $Data::Dumper::Indent = 0;
print Dumper +(fold_tree \&tree)->([1, [2, [[3, 4], 5]]]);
print "\n";
}
# The result is $VAR1 = [1,[2,[[3,4],5]]];
このfold_tree を使うには新たなF代数を作ってやればよい。例えば、二分木内の全ての要素の合計を求めたければ、以下のようなF代数 Int+Int*Int→Int に対するcatamorphismを算出するとよい。
print fold_tree(sub { @_ == 1 ? $_[0] # type Int : $_[0] + $_[1]; # type Int*Int })->([1, [2, [[3, 4], 5]]]), "\n"; # The result is 15
余談
Lambek's Lemmaより始代数は同型射となるので、A+X*X→X が全単射*2となるようなXと関数を見つければ、それが始代数の候補となる。Xを二分木とするとこの条件を満たしてくれる。・・・ってことでいいんじゃないかなと思う。
