Combinatorial Spiecies

• Combinatorial Spieciesという考え方がある
• 離散データ構造の定義が与えらえた時に、それを特定の要素数で構成するとして、その構成インスタンスの個数を数え上げることを考える
• 数え上げるにあたって、母関数を使う
• 圏論的に考えることができる
• ある集合AとBとがあって、全単射になっているとする
• あるspieciesがあると、Aに対応してF[A]というデータ構造インスタンスのの集合ができる。Bに対応してF[B]なるデータ構造インスタンスの集合ができる。AとBとが全単射だったが、F[A]とF[B]も全単射
• 今、データ構造を決めるspieciesが２つあって、FとGであるとする
• 母関数をそれぞれf(x),g(x)とする
• 母関数の演算をいくつか定めることにする
• f(x)+g(x),f(x)*g(x),g(f(x))など
• これらも母関数であるとして、対応集合の要素数から構成できるデータ構造のインスタンス数の母関数とする
• そんなとき、それぞれの母関数式f(x)+g(x),f(x)*g(x),g(f(x))に対応させて、どういうspieciesを考えればよいかを考えると便利である
• そんな話