Haskellでラムダ計算：乗算編

加算に引き続いてラムダ計算の乗算についてやっていきます。
乗算のラムダ式は以下のようになります。

$$\lambda x y a .x(ya)$$

例えば、$3$かける$3$は
$$(\lambda x y a .x(ya))\textbf{3}\textbf{3}\rightarrow\lambda a.\textbf{3}(\textbf{3}a)$$

$$\textbf{3}a\equiv(\lambda s z.s(s(s(z))))a\rightarrow\lambda z.a(a(a(z)))$$

$$(\textbf{3}a)b\rightarrow a(a(a(b)))$$となるので、

$\textbf{3}(\textbf{3}a)b = (\lambda s z.s(s(s(z))))(\textbf{3}a)b$
$\rightarrow[\textbf{3}a]([\textbf{3}a]([\textbf{3}a]b))$
$\rightarrow[\textbf{3}a]([\textbf{3}a](a(a(a(b)))))$
$\rightarrow a(a(a(a(a(a(a(a(a(b)))))))))$

two s z     = s(s(z))     -- 2
three s z   = s(s(s(z)))  -- 3
mult x y a = x(y a)
add1 x = x + 1

main = do
    print $ mult three three add1 0     -- 3 * 3
    print $ mult two three add1 0       -- 2 * 2

ghci> main
9
6