この記事は，代数的データ型と代数の関係について調べたことを個人的な解釈でまとめたものです．
（Qiita練習用の記事です．）
#データ型の要素数について
唐突ですが，あるデータ型の要素の数を数えたいと思います．
たとえば，次のデータ型$A$があったとします．
A=\{1,2,3,4\}
このデータ型は，1,2,3,4のいずれかしかとることができません．
このデータ型$A$の要素の数は，要素がいち，に，さん，よん，と4つあります．データ型の要素を表す数字とは一切関係なく，要素の数を数えているだけです．このように，データ型は要素の数を数えることができます．
いちいちデータ型に対するデータの要素の数を数えるのは面倒なので，データ型の要素の数を$N(A)$で表すことにします．この$A$の場合，$N(A)=4$ですね．
#代数的データ型について
代数的データ型の正確な定義は私は知りません．ですが，ここではどんなものが代数的データ型なのかについて述べます．
代数的データ型を作る方法としてよく使われるものとしては，もともとあったデータ型に対して，直和型という方法でデータ型を新しく作る方法と，直積型という方法でデータ型を新しく作る方法があります．
直和型でデータ型を作る
直和型でデータ型を新たに作る方法は，もともとのデータ型の，直和をとることです．そのままですね．これでは説明になっていないので，具体的な例を見てみましょう．
まず，データ型$A$，$B$が次のように定義されているとします
A=\{1,2,3,4\},
B=\{5,6,7,8\}
この２つデータ型の直和をとって，新しいデータ型$C$を作ると，次のようになります．
C=\{1,2,3,4,5,6,7,8\}
つまり，2つのデータ型の要素を両方とも要素にできるようなデータ型をつくるということです．簡単ですね．
ここで，$C$が$A$と$B$の直積をとって作られたデータ型であるということを表すために，直和の記号$\oplus$を使って，$C=A\oplus B$と書くことにしましょう．
直積型でデータ型を作る
直積型でデータ型を新たに作る方法は，もともとのデータ型の，直積をとることです．そのままですね．これでは説明になっていないので，具体的な例を見てみましょう．
まず，データ型$A$，$B$が次のように定義されているとします
A=\{1,2\},
B=\{5,6,7\}
この２つデータ型の直積をとって，新しいデータ型$C$を作ると，次のようになります．
C=\{(1,5),(1,6),(1,7),(2,5),(2,6),(2,7)\}
つまり，2つのデータ型から1つずつ要素を取り出して，組にしたものを（すべて）要素としたデータ型をつくるということです．簡単ですね．
ここで，$C$が$A$と$B$の直積をとって作られたデータ型であるということを表すために，直積の記号$\otimes$を使って，$C=A\times B$と書くことにしましょう．
直積はとる順番が逆だと，違うデータ型になります．例えば，$D=B\otimes A$は次のようになります．
D=\{(5,1),(5,2),(6,1),(6,2),(7,1),(7,2)\}
$(5,1)\neq(1,5)$です．
##直積直和複合型
直積を使ってデータ型をつくれて，直和型を使ってデータ型を作れるなら，その両方を使ってデータ型を作れると考えるのが自然でしょう．では，やってみます．
まず，データ型$A$，$B$が次のように定義されているとします
A=\{1,2\},
B=\{5,6\}
データ型$E=(A\otimes B)\oplus B$は，次のようになります．
E=\{(1,5),(1,6),(2,5),(2,6),5,6\}
組と組でないものが混じって何だか変な感じがしますが，これで大丈夫です．
##再帰的データ型
データ型を作るときに，定義しようとしているデータ型それ自身を入れ子にしても良いです．再帰的です．
データ型$A$が次のように定義されているとします．
A=\{1,2\}
このとき再帰的データ型$F=A\oplus (A\otimes F)$は，次のようになります．
F=\{1,2,(1,1),(1,2),(2,1),(2,2),(1,1,1),(1,1,2),(1,2,1),(1,2,2),...\}
再帰的にデータ型を定義しているので，このデータ型の要素を書ききることができませんでした.すみません．
データ型の定義$F=A\oplus (A\otimes F)$から，同じデータ型を表すデータ型を式変形でつくることができます．
F=A\oplus (A\otimes F)\\
=A \oplus (A \otimes ( A \oplus (A \otimes F))\\
= A \oplus (A \otimes A) \oplus (A \otimes A \otimes F)
定義式の右辺の$F$に定義式を代入して，整理しただけです．式変形することで，わかりやすくなったと思います．この式変形を無限回繰り返せば，
F= A \oplus (A \otimes A) \oplus (A \otimes A \otimes A) \oplus ...
となります．つまり，$F$は，Aを任意回直積して得られるデータ型の要素の全体だったわけですね．
#データ型を色々作ってみる
データ型の作り方が分かり，楽しくなってきたので，この際いろいろデータ型を作っていきましょう！
##ボイド型
何もない，そんなデータ型があります．ボイド型です．ボイド型は，要素が一つもありません．つまり次のデータ型$\phi$のことです．
\phi = \{\}
無さ過ぎですね．
##ユニット型
何もないわけではないが，一つしかありません．ユニット型です．ユニット型は，要素が一つしかありません．つまり次のデータ型$U$のことです．
U = \{()\}
ユニット型$U$は，要素が$()$の1つしかありません．
リスト型
リスト型として，次のようにデータ型$L[A]$を定義します．
L[A] = U \oplus (A \otimes L[A])
$L[A]$の$[A]$は，データ型が，他のデータ型$A$に基づいて作られるということを表すことにします．$U$は，ユニット型です．
$L(A)$を式変形すると，次のようになります．
L[A] = U \oplus (A \otimes U)\oplus (A \otimes A \otimes U)...)
仮に，$A=\{0,1\}$とすると，
L[A] = \{ () , (0,()),(1,()),(0,0,()),(0,1,()),(1,0,()),(1,1,()),(0,0,0,())...\}
かっこが多くて非常にわかりにくいですが，要するにデータ型$A$のリストを表現できるデータ型ということです．空のリストを$()$で表現していますね．
##ツリー型
ツリー型として，次のようにデータ型$T[A]$を定義します．
T[A] = U \oplus (A \otimes T[A] \otimes T[A])
これは，二分木のデータ構造を表すことのできるデータ型です．
#ワンホール型でデータ型をつくる
というように，データ型はたくさん定義できますが，本題のデータ型は次のようなものです．
何かしらのデータ型をもとにした，穴の開いたデータ型，ワンホール型を作ります．
すなわち，データ型の要素に，一つだけ穴$()$が開いたような要素を全部集めてきたものを新しいデータ型として定義します．
具体例を出します．
データ型$A$が次のように定義されているとします．
A=\{1,2\}
すると，$A$のワンホール型は，$A$から要素を取り出してきて，その要素に1つだけ穴$()$をあけてつくります．$A$の要素は$1$,$2$です．$A$から$1$を取り出して，1つだけ穴をあける方法は，1を穴$()$に変えるしかないです．$2$も同じ穴$()$に変わります．よって$A$のワンホール型は，次のようになります．ただし，$A$のワンホール型を$H[A]$で表すことにします．
H[A]=\{()\}
ユニット型になってしまいました．
では，$H[A\otimes A]$はどうでしょうか．$A\otimes A$の要素は$(1,1),(1,2),(2,1),(2,2)$
です．$(1,1)$に一つ穴$()$をあける方法は2通りあり，$(1,()),((),1)$です．$A\otimes A$のすべての要素について1穴を空けるてデータ型を構成すると，次のようになります．
H[A\otimes A]=\{(1,()),(2,()),((),1),((),2)\}
#要素数再び
いろいろなデータ型やデータ型の構成方法がそろってきたので，それらのデータ型の要素の数を調べてみましょう．といっても，特定のデータ型に対してだけ話すのは一般性に欠けるので，「要素数が$a$個あるデータ型」のように代数を導入しましょう．そして，そのようなデータ型について，直積・直和など今まで定義してきた方法で新しくデータ型を作ったとき，要素数がいくつになるか調べましょう．
データ型$A$の要素数$L(A)$が，aだったとします．またデータ型$B$の要素数が，$b$だったとします．($L(A)=a,L(B)=b$)．
直和型
直和でデータ型を構成すると，要素数は，もともとのデータ型の個数の和になります．すなわち，
N(A\oplus B)=N(A)+N(B)=a+b
です．上のほうの具体例を見ると，一目瞭然ですね．
直積型
直積でデータ型を構成すると，要素数は，もともとのデータ型の個数の積になります．すなわち，
N(A\otimes B)=N(A)N(B)=ab
です．上のほうの具体例を見ると，一目瞭然ですね．
##リスト型
リスト型は，直積型と直和型の組み合わせでできているので，直積型と直和型の要素数の求め方を組み合わせることで要素数を求めることができそうです．
N(L[A]) = N(U \oplus (A \otimes L[A]))\\
=N(U)+N(A\otimes L[A])\\
=1+N(A\otimes L[A])\\
=1+N(A)N(L[A])\\
=1+aN(L[A])
右辺にもリスト型の要素が出てきてしまっているので，これを整理すると，次のようになります．
N(L[A]) = \frac{1}{1-a}
これが，リスト型の要素数です．
ちょっと待ってください．要素数$a$は1を超える場合があるはずです．そのときに，この式はマイナスになり，分数になってしまいます．どういうことでしょうか？これは，この式を級数展開することで解決できます．すなわち，
\frac{1}{1-a} = 1 + a + a^2 + a^3 + ...
となり，これは第一項が空のリストの要素数，第二項が長さ１のリストの要素数，第三項が長さ２のリストの要素数...というわけで，それらを全て足しているので，リストのすべての要素の数となっています．
##ツリー型
リスト型と同じように，要素数を求めます．
N(T[A]) = N(U \oplus (A \otimes T[A] \otimes T[A]))
=N(U)+N((A \otimes T[A] \otimes T[A]))\\
=1+N((A \otimes T[A] \otimes T[A]))\\
=1+N(A)N(T[A])^2\\
=1+aN(T[A])^2
これは，二次方程式$0=1+N(T[A])+aN(T[A])^2$ですから，これを解くと．
L(T[A])=\frac{1-\sqrt{1-4a}}{2a}
となります．もはや無理数と虚数まで含む要素数ですが，級数展開によって，次のように表せます．
\frac{1-\sqrt{1-4a}}{2a} = 1 + a + 2a^2 + 5a^3 +...
これは第一項が空のツリーの要素数，第二項が高さ１のツリーの要素数，第三項が高さ２のツリーの要素数...というわけで，それらを全て足しているので，ツリーのすべての要素の数となっています．
余談ですが，この級数展開の係数は，カタラン数になっています．
#ワンホール型の要素数
本題の本題です．では，ワンホール型の要素数はどうなるでしょう．
A=\{1,2\}
のワンホール型は，
H[A]=\{()\}=U
でした．$A$の要素数が$a$であるときも，同じように考えれば，$()$しかないので，1です．すなわち，
N(H[A])=1
です．
次に，$A\otimes A$のワンホール型の要素数を調べます．$A\otimes A$の要素数は$a^2$ですが，
A={1,2}のとき\\
H[A\otimes A]=\{(1,()),(2,()),((),1),((),2)\}
でした．よく考えると，これは
(A\otimes U) \oplus (U \otimes A)=\{(1,()),(2,()),((),1),((),2)\}
と同じです．これは，Aがどんな時でも成り立ちます．ですから，$A$の要素数が$a$のとき，
N(H[A\otimes A])=N((A\otimes U) \oplus (U \otimes A))=2a
となります．次は，$A\otimes A \otimes A$です．このデータ型の要素数は$a^3$です．
そして，このデータ型のワンホール型は，次のように表せます．
H[A\otimes A \otimes A] = (U\otimes A\otimes A) \oplus (A \otimes U \otimes A) \oplus (A \otimes A \otimes U)
ですから，要素数は，
N(H[A\otimes A \otimes A]) = N((U\otimes A\otimes A) \oplus (A \otimes U \otimes A) \oplus (A \otimes A \otimes U))=3a^2
すでに気づいた方もいらっしゃると思いますが，もともとのデータ型の要素数と，それに対応するワンホール型の要素数を比較してみます．
a \Leftrightarrow 1\\
a^2 \Leftrightarrow 2a\\
a^3 \Leftrightarrow 3a^2
なんと，ワンホール型の要素数は，もとのデータ型の微分になっています！
この関係はConor McBride氏が発見したもので，データ型のワンホール型の要素数は，データ型の要素数の微分になるという発見です．
これは代数的データ型と代数を関連付ける，重要な発見であると言えそうです．
この関係を使って，ツリー型のワンホール型というような，一見要素数が求めにくいものも，求めることができます．
ツリー型のワンホール型の要素数はツリー型の要素数の微分であるから，
L(T[A])=\frac{\partial }{\partial a}\frac{1-\sqrt{1-4a}}{2a} = \frac{(3-4a)\sqrt{1-4a}-(1-4a)}{2a(1-4a)}\\=1+4a+15a^2+56a^3+...
となります．
#参考文献
http://strictlypositive.org/diff.pdf
http://chris-taylor.github.io/blog/2013/02/10/the-algebra-of-algebraic-data-types/