因為有人提到，所以複習了一下..
1. Y combinator in Haskell
Y combinator 在 untyped lambda calculus 中是
\f -> (\x -> f (x x)) (\x -> f (x x))
試著寫成 Haskell:
y :: (a -> a) -> a
y f = (\x -> f (x x)) (\x -> f (x x))
f 的型別是 a -> a, 而 y 取 f 的 fixed-point，
所以 y 的型別是 (a -> a) -> a.
但是這個型別一看就有問題：把 type 看成邏輯的話，
這個 type 若有證明就會有 inconsistency. 果然， Haskell
不讓這個程式 typecheck:
Occurs check: cannot construct the infinite type: t = t -> a
Probable cause: `x' is applied to too many arguments
In the first argument of `f', namely `(x x)'
In the expression: f (x x)
操作上的理由是：在 (x x) 之中，x 的型別又是 t -> a, 又是 t, 而
t = t -> a 遞迴定義。
解決方法也很簡單，就頭痛醫頭腳痛醫腳，做一個 t 與 t -> a
同構的遞迴型別囉。
data Fix a = Rec (Fix a -> a)