再帰代数データ型と代数 - ラシウラなるほどなと思った A Neighborhood of Infinity: MSFP 2008 より HaskellでのListデータ型の定義 data List A = Nil | Cons A (List A) 各項を以下の数式記号に、置き換える List A => L(A) a | b => a ＋ b Nil => 1 Cons A b => A × b L(A) = 1 ＋ A × L(A)L(A)を左辺へまとめる (1 - A) × L(A) = 1係数で割る L(A) = 1 / (1 - A)テイラー展開する テイラー展開 - Wikipediaの幾何級数 L(A) = 1 ＋ A ＋ A^2 ＋ A^3 ＋ ...各項は、 A = A × 1 A^2 = A × A × 1 A^3 = A × A × A × 1 L(A) = 1 ＋ A × 1 ＋ A × A × 1
