Catamorphism の他の例

Catamorphismを使って二分木での畳み込みを定義すると比べると関連が見えてくるかも？

リストの畳み込み

自己関手Fとして、型Xを1+A*Xへ移すものをとる。1+A*ArrayRef A→ArrayRef A なる以下のF代数が始対象となる。

sub array(;$$) {
    @_ == 0 ? []                 # type 1
            : [$_[0], @{$_[1]}]; # type A*ArrayRef A
}

Catamorphism を算出するfoldl::(1+A*X→X)→ArrayRef A→X は以下。

sub foldl(&) {
    my $f = shift;

    my $result = $callee = sub {
        my $array_ref = shift;
        if (@$array_ref == 0) {
            return $f->();
        } else {
            my ($cur, @cdr) = @$array_ref;
            return $f->($cur, $callee->(\@cdr));
        }
    };
    Scalar::Util::weaken $callee;

    return $result;
}

これにより、所謂foldlの処理を実現できる。

# length
print +(foldl {
    @_ == 0 ? 0          # type 1
            : 1 + $_[1]; # type A*Int
})->([2, 6, 4]);
print "\n";

# sum
print +(foldl {
    @_ == 0 ? 0              # type 1
            : $_[0] + $_[1]; # type Int*Int
})->([2, 6, 4]);
print "\n";

自然数への適用

自己関手Fとして、型Xを1+Xへ移すものをとる。1+N→N なる以下のF代数が始対象となる(ただし、1 = {*}, N = {0, 1, 2, ...})。

sub succ(;$) {
    @_ == 0 ? 0          # type 1
            : $_[0] + 1; # type N
}

Catamorphism を算出するfold_maybe::(1+X→X)→N→X は以下。

sub iterate(&) {
    my $f = shift;

    my $result = $callee = sub {
        my $n = shift;
        $n == 0 ? $f->() : $f->($callee->($n - 1));
    };
    Scalar::Util::weaken $callee;

    return $result;
}

これは、関数をn回適用する効果をもたらす。

# repeat 'X'
print +(iterate {
    @_ == 0 ? ''          # type 1
            : $_[0] . 'X' # type String
})->(16), "\n";

# The result is "XXXXXXXXXXXXXXXX"

# power of 2
print +(iterate {
    @_ == 0 ? 1         # type 1
            : $_[0] * 2 # type Int
})->(4), "\n";

# The result is 16

余談

いずれの例も、始代数が同型射であることを利用し、その逆関数を用いてCatamorphism の生成関数を作っている。例えば自然数の例だと、0 -> () ∈ 1、n -> n - 1 ∈ N が始代数の逆関数。でもって、F代数の射の可換性から、() ∈ 1 に関しては $f->() に移る必要があり、$n - 1 ∈ Nは $f->($callee->($n - 1)) に移る必要がある。すなわち、$callee->(0) = $f->() に移り、$callee->($n) = $f->($callee->($n - 1)) ( $n > 0 ) が求まる。