読者です 読者をやめる 読者になる 読者になる

北海道苫小牧市出身の壮年PGが書くブログ

永遠のプログラマを夢見る、苫小牧市出身のおじさんのちらしの裏

Catamorphismを使って二分木での畳み込みを定義する

perl perl+web math

高階関数がなす圏上の自己関手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を二分木とするとこの条件を満たしてくれる。・・・ってことでいいんじゃないかなと思う。

*1:これは計算して確かめる必要あり。後述のfold_tree がその答えだけど。

*2:1対1対応。逆関数が存在する