リストとスタック
忘れてしまう件、メモに動機や例を書いておかないのがいけないのだと思った。そのときは、具体的な事例で考えているので自明に見えることでも、その例がなくなるとサッパリわからなくなる。
リストとスタックの関係
で具体例。Lispのリストのようなものを考える、ただし再帰構造は考えないで、基本的な値の領域はAとする。S=A*と考えてよい。
nil:1→S
cons:A×S→S
car:S→A
cdr:S→S
一方、Aのスタックを考えると：
細かいことを言わなければ、これは同型。
Stack:1→S （コンストラクタ）
push:S×A→S
top:S→A
pop:S→S
（非再帰の）リストからcarを除くと：
nil:1→S
cons:A×S→S
cdr:S→S
スタックからコンストラクタを除くと：
push:S→SA
top:S→A
pop:S→S
この状況で、リストは、1次多項式関手F(X)=1+A+Xの代数、スタックは一般ベキ単項式関手G(X)=A×X×XAの余代数である。
おおざっぱに言えば、リストは代数でスタックが余代数、そして同型となる。だが、正確に言えばそうではない。この「おおざっぱな主張」と「正確な主張」の差をキッチリと説明できないか？ それが問題意識。
代数対
上の議論で、リストのcarとスタックのコンストラクタは邪魔なので除いた。が、考えないわけにもいかないので、やっぱり入れておく。
nil:1→S
cdr:S→S
cons:A×S→S
-
-
-
-
-
-
-
-
-
- -
-
-
-
-
-
-
-
-
car:S→A
Stack:1→S （コンストラクタ）
-
-
-
-
-
-
-
-
-
- -
-
-
-
-
-
-
-
-
top:S→A
pop:S→S
push:S→SA
carは定数関手C(X)=Aの余代数、コンストラクタは定数関手I(X)=1の代数である。この例から両代数（dialgebra）を考えてもよいが、まずはそのまんまの定式化：
- F, GをC上のendo-functorとして、F代数α:F(S)→S と G余代数β:S→G(S)の組(α, β)を代数対と呼ぶ。
しかし、普通に射（準同型）を定義すると、リストとスタックの同型は定義しようがない。代数+余代数に分解可能な両代数の範囲で考えるか、あるいは、1次多項式関手と一般ベキ単項式関手を特論的に扱うか？
