1. 圏を考える
Perlのスカラ値の任意の集合を対象として、引数も戻り値も一つで副作用がないサブルーチンを射とします*1。domとcodについては、関数が正常に動作する範囲で適当にとりましょう。
* 例: 対象「文字列」から対象「整数」への射 length
2. 自己関手の表現
自己関手は、二つの写像からなります。
3. 自然変換の表現
関手Tから関手Sの自然変換は、対象Aを「TAからSAへの射」に移す写像です。対象に対する各射を、自然変換のコンポーネントと呼びます。定義から、コンポーネントは対象の数だけ存在します。
ですが、今回は「Perlのスカラ値全体を関手Tで移した集合から関手Sで移した集合へのサブルーチン」1個だけを自然変換とし、これによって全部のコンポーネントを表現します。各集合に対するコンポーネントは、このサブルーチンを集合で制限したものと考えます。
まとめると、自然変換は『関手T_objectの世界の値を引数とし、関手S_objectの世界の値を返すサブルーチン』として表現できます。
4. 各種合成の実装
合成射
圏なので射の合成を定義します。単なる関数の合成です。
sub comp{ my ($arrow1, $arrow2) = @_; return sub { return $arrow1->( $arrow2->(@_) ); } }
自然変換同士の合成(垂直)
自然変換の合成は、コンポーネントの射同士の合成となります。今回は一つのサブルーチンで自然変換を表してるので、実装は単なる関数の合成です。
なお、nt は natural transformation の略です。
sub nt_nt{ my ($nt1, $nt2) = @_; # 各対象に対するコンポーネントを合成(今回は全部同じコンポーネント) comp $nt1, $nt2; }
関手と自然変換の合成(水平)
関手と自然変換を合成すると、新たな自然変換となります。この合成は可換ではなく、順番によって意味が変わります。
まず、関手と自然変換を合成する場合の各コンポーネントは、自然変換の各コンポーネントである射を関手で移した射になります。なお、$Tは関手の「射を移す写像(T_arrow)」です。
sub T_nt{ my ($T, $nt) = @_; return $T->($nt); }
次に、自然変換と関手を合成する場合の各コンポーネントは、対象を関手で移したものに対応する自然変換のコンポーネントとなります。今回は任意の対象に対してコンポーネントは一つなので、この合成では自然変換は変わりません*3。
sub nt_T{ my ($nt, $T) = @_; # 対象TAによる$ntのコンポーネントだが、 # 任意の対象について同じコンポーネントとしているので何もしなくていい return $nt; }
5. モナドの定義
モナドは、関手と二つの自然変換からなる*4ので、その通りに定義します。モナドは (T, μ, η) と書きますが、これら三つでモナドだと言う意味合いを強調するために一つのオブジェクトにこれら３つを持たせます。
package Monad; use Moose; # 自己関手 (射の写像) has T_arrow => ( isa => 'CodeRef', is => 'ro', required => 1, ); # モナドの単位元となる自然変換 (ID -> T) has eta => ( isa => 'CodeRef', is => 'ro', required => 1, ); # モナドの乗法となる自然変換 (TT -> T) has mu => ( isa => 'CodeRef', is => 'ro', required => 1, ); sub flat { my $self = shift; return sub { my $arrow = shift; # A -> TB # TA -> TB return comp $self->mu, $self->T_arrow->( $arrow ); } } no Moose; 1;
役者はこれで揃ってるのですが、当然この3要素はなんでもいいわけじゃなく、色々な条件を満たす必要があります。
なお、 Kleisli triple を構成するための flat も定義しました。flat は T_allow、eta、mu から定義が可能です。
6. Listモナドを作る
Haskell の Listモナド っぽいものを実装し、どんな条件を満たしてればモナドになれるのか見て行きます。以下のように定義するとモナドになります。
my $list_monad = Monad->new( T_arrow => sub { my $arrow = shift; # A -> B return sub { my $tx = shift; # TA -> TB return [map { $arrow->($_) } @$tx]; }; }, eta => sub { return [ shift ]; }, mu => sub { my $TTval = shift; # an array of arrays. return [ map {@$_} @$TTval ]; }, );
なお、実装はしませんがT_objectも考えておく必要があります。これは、「元の集合を任意個含む配列リファレンスの集合」としておきます。
- 例: 対象「文字列」をT_objectで移すと、対象「文字列を含む配列へのリファレンス」となる
- 例: 対象「数字」をT_objectで移すと、対象「数字を含む配列へのリファレンス」となる
さて、以下で各条件を見ていきますが、これらは本当は射に対する等価性です。つまり、本来なら関数がイコールであることを見なければならないのですが、Perlではそれはできないので、適当な値を渡して実験してます。よって、厳密に言うと以下のチェックは必要条件にしかなってません。
A). 関手T_arrowの条件
T_arrowが関手です。関手は、恒等射を恒等射に移します。また、射の合成を保存しなければなりません。
{
# Tが関手か(恒等射)
my $id = sub { $_[0] };
my $Tid = $list_monad->T_arrow->($id);
my $v = [ {key1 => 1, key2 => 2}, {key1 => 3, key2 => 4}, ];
is_deeply(
$Tid->($v),
$v,
);
}
{
# Tが関手か(合成の保存)
my $f = sub { length shift };
my $g = sub { '*' x shift };
my $TgTf = comp $list_monad->T_arrow->($g), $list_monad->T_arrow->($f);
my $Tgf = $list_monad->T_arrow->(comp $g, $f);
my $v = ['abc', 'defg', 'hijklm'];
is_deeply( # expected:[ '***', '****', '******' ]
$TgTf->($v),
$Tgf->($v),
);
}
B). 自然変換の条件
自然変換の条件は以下です(可換図式は省略)。etaとmuが自然変換です。
{
# etaが ID->T の自然変換か
my $f = sub { shift =~ /\.html$/ };
my $f_eta = comp $list_monad->T_arrow->($f), $list_monad->eta;
my $eta_TF = comp $list_monad->eta, $f;
my $v = 'test.html';
is_deeply( # expected: [ 1 ]
$f_eta->( $v ),
$eta_TF->( $v ),
);
}
{
# muが TT->T の自然変換か
my $f = sub { uc shift };
my $Tf_mu = comp $list_monad->T_arrow->($f), $list_monad->mu;
my $mu_TTF = comp $list_monad->mu, $list_monad->T_arrow->($list_monad->T_arrow->($f));
my $v = [[ 'perl', 'python', 'haskell' ]];
is_deeply( # expected: [ 'PERL', 'PYTHON', 'HASKELL' ]
$Tf_mu->( $v ),
$mu_TTF->( $v )
);
}
C). モナドの条件
モナドは自然変換に関する２つの図式を可換にします。図式は省略しますが、muを乗法とした結合則と、etaの単位元則です。
{
# モナドの結合則
my $T_mu = T_nt $list_monad->T_arrow, $list_monad->mu;
my $mu_T = nt_T $list_monad->mu, $list_monad->T_arrow;
my $mu_T_mu = nt_nt $list_monad->mu, $T_mu;
my $mu_mu_T = nt_nt $list_monad->mu, $mu_T;
my $v = [ [ [1,2] ], [ [3, 4], [5, 6] ] ];
is_deeply( # expected: [ 1, 2, 3, 4, 5, 6 ]
$mu_T_mu->($v),
$mu_mu_T->($v),
);
}
{
# モナドの単位元
my $T_eta = T_nt $list_monad->T_arrow, $list_monad->eta;
my $eta_T = nt_T $list_monad->eta, $list_monad->T_arrow;
my $mu_T_eta = nt_nt $list_monad->mu, $T_eta;
my $mu_eta_T = nt_nt $list_monad->mu, $eta_T;
my $v = [1, 2, 3];
is_deeply(
$mu_T_eta->($v),
$v,
);
is_deeply(
$mu_eta_T->($v),
$v,
);
}
D). Kleisli triple
C). を満たせばKleisli tripleになってるのは確実なのですが、flatのテストのために確かめます。これらは、Haskellのいわゆるモナド則となります。
{
# Kleisli triple (1)
my $flaten_eta = $list_monad->flat->( $list_monad->eta );
my $v = [2,3,4];
is_deeply(
$flaten_eta->( $v ),
$v,
);
}
{
# Kleisli triple (2)
my $f = sub { [ ( 0 ) x $_[0] ] };
my $flaten_f_eta = comp $list_monad->flat->($f), $list_monad->eta;
is_deeply( # expected: [ 0, 0, 0, 0 ]
$f->(4),
$flaten_f_eta->(4),
);
}
{
# Kleisli triple (3)
my $f = sub { [ split / /, shift ] };
my $g = sub { [ split /,/, shift ] };
my $left = comp $list_monad->flat->($g), $list_monad->flat->($f);
my $right = $list_monad->flat->(comp $list_monad->flat->($g), $f);
my $v = ["ABC DEF", "GH, IJK", "LM N,OP"];
is_deeply( # expected: [ 'ABC', 'DEF', 'GH', 'IJK', 'LM', 'N', 'OP' ]
$left->($v),
$right->($v),
);
}
