再帰代数データ型と代数

なるほどなと思った

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)

テイラー展開する

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  
    ＋ A × A × A × 1  
    ＋ ...

最初の変換を逆適用

  • L(A) => List A
  • a ＋ b => a | b
  • 1 => Nil
  • A × b => Cons A b 
List A = Nil 
       | Cons A Nil 
       | Cons A (Cons A Nil)
       | Cons A (Cons A (Cons A Nil))
       | ...


あと、

  • 微分 <=> データの各所に穴を開けたもの

らしく、Listの場合、

L(A) = 1 + A L(A)

両辺を微分すると、

L'(A) = L(A) + A L'(A)

かつ、両辺にL(A)をかけると、

L(A)^2 = L(A) + A L(A)^2

よって

L'(A) = L(A)^2

となり、Listに穴を開けるとList二つ組になるとのこと